Reproduce “Polynomially larger deletion codes by linear hashing of substring counts” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Eyal En Gad
The authors construct fixed-alphabet codes correcting up to t insertions, deletions, and substitutions with redundancy at most (2t−1)log_q n+O_t(log_q log_q n). For two binary deletions, the upper-bound coefficient is 3, down from 4, while the lower-bound coefficient is 2. Redundancy is measured in q-ary symbols. The probabilistic construction uses random linear hashes of substring counts; explicit construction and optimality remain open.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.