Papers for

error correction system engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Coding agents improve DNA barcode sets with edit distance codes

Coding Agents for Coding Theory

Abstract: We spent five weeks using an LLM coding agent on open problems in coding theory: finding large sets of four-letter words, such as DNA barcodes, that stay far apart in edit distance. The agent wrote the verifiers and search code; a human chose the problem and set the verification protocol. Restricting the search to codes with a prescribed symmetry, a classical technique, shrank the problem about fourfold and raised the best known code of length 6 and minimum edit distance 3 from 114 to 120 words ($E_4(6,3) \geq 120$). The same pipeline improved twelve further lower bounds at lengths 6 to 9 and distances 3 to 6. We give the failures equal space. Our own search stopped at 116 and recorded the last symmetry class as topping out at 112; a second agent session, running the same search with a better operator, found the 120. A later verdict that the method did not carry over to length 7 was wrong for the same reason, and an earlier instance cost three weeks. Each time, an intermediate result was written down, never rechecked, and treated as a fact that ruled out further search. Checking final outputs, as our protocol required, does not catch such errors.

Wed 30 SeptInformation TheoryArtificial IntelligenceMachine Learning
The gist
The authors explored using a language model coding agent to tackle hard problems in coding theory, specifically finding sets of four-letter words like DNA barcodes that differ sufficiently from each other. They let the agent write code to check and search for these sets while a human chose the problem and verified results. Using classical symmetry restrictions, they found bigger sets than previously known, improving best known codes of a certain length and edit distance. The study also highlighted common errors in verifying intermediate results that can mislead further searches, showing that carefully checking only final answers is not enough.
Open → 2609.39081v1