Beyond the Johnson Bound: A Path to Smaller Post-Quantum SNARKs

What mathematics lies behind the Ethereum Foundation's $1M Proximity Prize, and why does it matter for cryptographic proofs?

This workshop builds an intuitive understanding of Reed Solomon codes, polynomial encoding, decoding radii, and the Johnson bound. We then introduce Mutual Correlated Agreement (MCA) through simple mathematical examples, giving participants the foundations needed to understand the central question of the Proximity Prize and why solving it is challenging.

We explore cutting edge research on soundness bounds beyond the Johnson bound, including recent results by Dao, Kominers, and Thaler, and discuss how stronger guarantees can reduce verifier queries and proof sizes in FRI and WHIR.

Finally, we introduce better.codes, Lean 4 formal verification, and opportunities to contribute to these open mathematical problems.

The workshop includes interactive quizzes and audience discussion. No prior coding theory background is required.

Speakers: Alexander John Lee, Andrei Ivasko

Track: Applied Cryptography