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

Duration: NaN:NaN:NaN

Speaker: Alexander John Lee, Andrei Ivasko

Type: Workshop

Expertise: Some familiarity with the topic

Event: Devcon

Date: Nov 2026

How can coding theory help shrink post quantum SNARKs? This workshop combines an introductory presentation with an interactive discussion, drawing on Arnon, Boneh, and Fenzi’s survey: https://eprint.iacr.org/2026/680. We build intuition for Reed Solomon list decoding, the Johnson bound, proximity gaps, and correlated agreement, then examine the late 2025 counterexamples to broad near capacity conjectures: what changed and what remains open. We connect these questions to FRI, WHIR, and STIR, and their relevance to leanVM and Lean Ethereum. Stronger bounds could mean fewer queries, smaller proofs, and cheaper verification at a fixed security level. The interactive segment gives participants space to explore the ideas and open questions together. We also introduce the $1M Proximity Prize and better.codes, its live companion challenge, and discuss whether Lean-assisted research can help advance the theory. No coding theory background is required. Prize: https://proximityprize.org/