(2026-04) Open Problems in List Decoding and Correlated Agreement
2026-04-07
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.