# Explicit two-deletion codes with redundancy matching the existential bound

arXiv: https://arxiv.org/abs/2007.10592 · HTML: https://mlsanity.com/paper/2007.10592/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2020.

## Built on by (most cited first, 2 of 2)

- [LLM-Guided Search for Deletion-Correcting Codes](https://mlsanity.com/paper/2504.00613/) (2025)
- [Deep Learning-Based Detection for Marker Codes over Insertion and Deletion Channels](https://mlsanity.com/paper/2401.01155/) (2024)

## Abstract (arXiv)

We give an explicit construction of length-n binary codes capable of correcting the deletion of two bits that have size 2n/n4+o(1). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Omega(2n/n4). Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size Omega(2n/n3+o(1)) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.