High Rate Efficient Local List Decoding from HDX
Yotam Dikstein, Max Hopkins, Russell Impagliazzo, Toniann Pitassi · 2026
Read High Rate Efficient Local List Decoding from HDX by Yotam Dikstein, Max Hopkins, Russell Impagliazzo, Toniann Pitassi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-22535.txt.
Introduction
Yotam Dikstein, Max Hopkins, Russell Impagliazzo, and Toniann Pitassi build a new kind of error-correcting code. Their codes can be decoded locally, by reading only a small part of a message, and they list a few possible answers when noise is heavy. The codes reach rates and error tolerance close to the best theory allows.
The decoding runs very fast and with shallow circuits. Paired with older codes for low-noise cases, the work settles several long-open problems in coding and complexity theory. Such codes help protect data and also power proofs about hard problems.
Catalog record
| CREATOR | Yotam Dikstein, Max Hopkins, Russell Impagliazzo, Toniann Pitassi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 459 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-22535