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

CREATORYotam Dikstein, Max Hopkins, Russell Impagliazzo, Toniann Pitassi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE459 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-22535

Browse the full library · About the Tower of Babel