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

CREATORDor Minzer, Kai Zhe Zheng
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE295 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-00346

Browse the full library · About the Tower of Babel