Improved Round-by-round Soundness IOPs via Reed-Muller Codes
Dor Minzer, Kai Zhe Zheng · 2025
Read Improved Round-by-round Soundness IOPs via Reed-Muller Codes by Dor Minzer, Kai Zhe Zheng (2025) 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-2504-00346.txt.
Introduction
Dor Minzer and Kai Zhe Zheng build, in a 2025 paper, a faster way for a verifier to check a claimed proof about error-correcting codes. Interactive oracle proofs let a checker sample tiny pieces of a long encoded proof instead of reading it all. The quality of such a system is set by how few samples it needs and how rarely a false proof slips through. The authors work with Reed-Muller codes, which encode messages as multi-variable formulas.
Their test checks random straight lines against single points, a shift from the grid-aligned tests used before. That change yields stronger soundness with fewer rounds and queries in a key range of settings. They also extend the result to a classic hard problem from logic. Along the way they add general tools that other proof builders can reuse.
Catalog record
| CREATOR | Dor Minzer, Kai Zhe Zheng |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 295 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-00346