Open Problems in List Decoding and Correlated Agreement

Gal Arnon; Dan Boneh; Giacomo Fenzi

Paper 2026/680

Open Problems in List Decoding and Correlated Agreement

Gal Arnon

, Bocconi University

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.

Note: July 2026 Update: Updated KKH comparison and concrete estimate of attacks. Added MCA lowerbound.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: proximity gaps correlated agreement list decoding proximity prize
Contact author(s): galarnon42 @ gmail com
dabo @ cs stanford edu
giacomo fenzi @ epfl ch
History: 2026-07-06: last of 3 revisions; 2026-04-07: received; See all versions
Short URL: https://ia.cr/2026/680
License: CC BY

BibTeX

@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}
}