Reproduce “An Improved Johnson Bound for List-Decoding with Hints” 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
Swastik Kopparty, Harry Sha
The authors show how a known codeword can improve list decoding by constraining other candidates through its coordinatewise agreement with a received word. For a Reed–Solomon code with distance 0.99, a hint at distance 0.85 supports decoding to radius 0.901, beyond the Johnson radius of 0.9. This is an illustrative example; guarantees require hints and depend on code and hint geometry.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.