4 papers
List Size of Random Linear Codes: Optimality and the Limits of Average-Radius List Decoding
Chen Yuan, Ruiqi Zhu
Guruswami, Li, Mosheiff, Resch, Silas and Wootters conjectured that, for every fixed prime power and , random linear codes of rate have li…
A Syndrome--Space Approach to Proximity Gaps and Correlated Agreement for Random Linear Codes and Random Reed--Solomon Codes
Chen Yuan, Ruiqi Zhu
Proximity gaps and correlated agreement have become central tools in the analysis of interactive oracle proofs of proximity (IOPPs) and code-based SNARKs. Informally, a proximity-g…
Randomness-Efficient Constructions of Capacity-Achieving List-Decodable Codes
Jonathan Mosheiff, Nicolas Resch, Kuo Shang +1
We wish to generate list-decodable codes over small alphabets using as little randomness as possible. Specifically, we hope to generate codes achieving what we term the Elias bound…
Tight Bounds on List-Decodable and List-Recoverable Zero-Rate Codes
Nicolas Resch, Chen Yuan, Yihan Zhang
In this work, we consider the list-decodability and list-recoverability of codes in the zero-rate regime. Briefly, a code is -list-recover…