Paper 2026/680

Open Problems in List Decoding and Correlated Agreement

Dan Boneh, Stanford University

Giacomo Fenzi, École Polytechnique Fédérale de Lausanne

Abstract

The Ethereum Foundation recently announced the Proximity Prize which aims to resolve some open problems that play an important role in the design of succinct proof systems. This paper reviews the open problems relevant to the Proximity Prize. We focus on some grand challenges relating to list decoding bounds, proximity gaps, correlated agreement, and mutual correlated agreement,as they relate to proof systems and Reed--Solomon codes. Along the way we survey the known results on these topics.

@misc{cryptoeprint:2026/680,
      author = {Gal Arnon and Dan Boneh and Giacomo Fenzi},
      title = {Open Problems in List Decoding and Correlated Agreement},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/680},
      year = {2026},
      url = {https://eprint.iacr.org/2026/680}
}