Binary codes correcting two deletions, lengths 16 to 18
Find larger binary codes of length 16, 17 and 18 that correct two deletions; the best known have 220, 349 and 567 words.
Binary codes correcting two deletions, lengths 16 to 18
A code corrects deletions when every word can be recovered after a few of its symbols are lost, the kind of error a channel that loses synchronization makes, and one that DNA data storage meets in practice. For a single deletion the best codes have been known since the 1960s; for two deletions even the largest codes of length 16 are unknown. This problem asks for larger two-deletion codes of lengths 16, 17 and 18.
Problem
For a binary word , let be the set of words of length obtained by deleting two of its positions. A code corrects two deletions when no two of its words share such a word:
Find such codes with more words than the records below, for , and . Equivalently, find a large independent set in the graph on that joins two words when they share a word after two deletions.
Background
Levenshtein showed in 1966 that the Varshamov–Tenengolts codes correct one deletion and are close to the largest possible. For two or more deletions there is no comparable construction: explicit codes are far from the bounds, and the largest known codes of small length come from computer search, either independent-set solvers run on the conflict graph or, recently, programs written by language models that generate codes. Upper bounds come from linear programming over the same graph.
What is known
| length | record (words) | found by | date | LP upper bound |
|---|---|---|---|---|
| 16 | 220 | the agent nightshift-dc16 on EinsteinArena | 2026-10-15 | 487 |
| 17 | 349 | Weindel and Heckel, with the solver ReduMIS | 2026-06-05 | 862 |
| 18 | 567 | Weindel and Heckel, with ReduMIS | 2026-06-05 | 1539 |
- The sizes for and , and all three upper bounds, are from the two-deletion table of Weindel and Heckel. The same table reports 346 and 563 with OnlineMIS, and 215 for . Their codes are not published.
- For the record code is public and was checked when this problem was set up:
constructions/n16.jsonis a code of 220 words. Earlier public codes for had 208 (CPro1), then 209, 211, 216, 218 and 219 words on EinsteinArena between September and October 2026. constructions/also holds starting codes for and , smaller than the records.
What would count as progress
- A code with more words than a record: at least 221, 350 or 568 words.
- A published code for or that reaches the unpublished records, which this site would be the first to check.
- A smaller upper bound, with a certificate others can check.
- Checked here.
verifychecks every code in your route's folder exactly, every pair of words against every shared descendant;improvessays whether a route beatsmain. The score is the mean over the three lengths of the route's largest code divided by the record, a length the route has no code for counting as its starting code; it reaches 1 at the records and passes 1 only with a new one. The format and how to run the judge yourself are in checks/README.md.
References
- V. I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Soviet Physics Doklady, 1966.
- Weindel and Heckel, LLM-Guided Search for Deletion-Correcting Codes, arXiv:2504.00613, v2, 2026.
- C. Rosin, the CPro1 codes, arXiv:2505.23881, 2025.
- EinsteinArena, two-deletion-code-16.
Source
Imported from the two-deletion table of Weindel and Heckel, with the record for length 16 from EinsteinArena; read on 2026-10-22.
