Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > PROXIMITY GAPS:
Reports tagged with proximity gaps:
TR26-232 | 6th October 2026
Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi

Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps

Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterman, Zhang, and Zheng, in a remarkable breakthrough, showed that Reed-Solomon (RS) codes over fields of large characteristic are algorithmically list-decodable all the way up to ... more >>>


TR26-235 | 8th October 2026
Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng

The One-and-a-Half Johnson Bound Is Tight for Proximity Gaps of General Linear Codes

For a linear code $C\subseteq\mathbb{F}_q^n$, we say that $C$ satisfies the \emph{proximity-gaps property} up to distance $\delta_1$ if, for every $\delta_2>\delta_1$ and every $f,g\in\mathbb{F}_q^n$, at least one of which is $\delta_2$-far from $C$ in relative Hamming distance, there are only a small fraction (typically at most $\operatorname{poly}(n)/q$) of \emph{exceptional coefficients} ... more >>>


TR26-237 | 9th October 2026
Quang Dao, Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng

Counterexamples to Beyond-Johnson Proximity Gaps over Binary Fields

Revisions: 1

Many hash-based proof systems check that committed words are close to Reed-Solomon codewords by testing one random combination of them. Their soundness analysis uses a proximity gap: if the combination agrees with a codeword on many positions, so do the original words, on the same positions, except for a few ... more >>>


TR26-262 | 20th October 2026
Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami

Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding

For any desired rate $R \in (0,1)$, and gap to list-decoding capacity $\varepsilon > 0$, we give an explicit $n^{O_{\varepsilon}(1)}$ time construction of Reed-Solomon codes over extension fields of size polynomial in the block length $n$ that can be list-decoded from a fraction $1-R-\varepsilon$ of errors with the optimal list-size ... more >>>




ISSN 1433-8092 | Imprint