Proofs, Codes, and Complexity
Event details
| Date | 15.10.2025 |
| Hour | 15:00 › 17:00 |
| Speaker | Ignacio Manzur |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Thomas Vidick
Abstract
A central aim of this thesis is to explore the intricate interplay between proof systems, coding theory, and computational complexity. Rooted in interactive proofs and probabilistically checkable proofs (PCPs), these systems provide deep insights into the boundaries of efficient verification. Error-correcting codes, with their emphasis on redundancy and resilience, supply the structural foundation that allows such verification to remain robust. Yet important challenges remain, especially in balancing verifier efficiency with proof length and soundness. Our work develops new constructions that draw directly on coding-theoretic principles, achieving improved trade-offs in proof design. Under this framework, we examine how local testability and decoding problems manifest as natural barriers in complexity-theoretic analysis. Revealing such barriers not only clarifies the limits of efficient proof verification but also deepens our understanding of hardness of approximation. Explicitly, we introduce locally testable proof frameworks inspired by modern coding theory. Additionally, we prove lower bounds that connect decoding hardness to inherent verification complexity. Linking these results to broader computational themes, we demonstrate implications for resource-bounded and streaming models. Lessons from this analysis show that proof systems and codes are not merely parallel tools but fundamentally intertwined. Yielding novel verification protocols, our constructions illuminate new directions in the theory of computation. Results presented here collectively advance the theoretical landscape. Expanding the PCP paradigm through coding-theoretic insights, they refine what is possible within probabilistic verification. As such, the thesis underscores the central role of redundancy and structure in efficient computation. Deep complexity-theoretic consequences follow, particularly regarding class separations and approximation hardness. In conclusion, this work unifies three threadsâproofs, codes, and complexityâinto a coherent narrative of interaction. New perspectives thus emerge, highlighting both the power and the limitations of efficient verification. Grounded in rigorous theory, these contributions help shape future research at the frontier of computational complexity.
Background papers
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Thomas Vidick
Abstract
A central aim of this thesis is to explore the intricate interplay between proof systems, coding theory, and computational complexity. Rooted in interactive proofs and probabilistically checkable proofs (PCPs), these systems provide deep insights into the boundaries of efficient verification. Error-correcting codes, with their emphasis on redundancy and resilience, supply the structural foundation that allows such verification to remain robust. Yet important challenges remain, especially in balancing verifier efficiency with proof length and soundness. Our work develops new constructions that draw directly on coding-theoretic principles, achieving improved trade-offs in proof design. Under this framework, we examine how local testability and decoding problems manifest as natural barriers in complexity-theoretic analysis. Revealing such barriers not only clarifies the limits of efficient proof verification but also deepens our understanding of hardness of approximation. Explicitly, we introduce locally testable proof frameworks inspired by modern coding theory. Additionally, we prove lower bounds that connect decoding hardness to inherent verification complexity. Linking these results to broader computational themes, we demonstrate implications for resource-bounded and streaming models. Lessons from this analysis show that proof systems and codes are not merely parallel tools but fundamentally intertwined. Yielding novel verification protocols, our constructions illuminate new directions in the theory of computation. Results presented here collectively advance the theoretical landscape. Expanding the PCP paradigm through coding-theoretic insights, they refine what is possible within probabilistic verification. As such, the thesis underscores the central role of redundancy and structure in efficient computation. Deep complexity-theoretic consequences follow, particularly regarding class separations and approximation hardness. In conclusion, this work unifies three threadsâproofs, codes, and complexityâinto a coherent narrative of interaction. New perspectives thus emerge, highlighting both the power and the limitations of efficient verification. Grounded in rigorous theory, these contributions help shape future research at the frontier of computational complexity.
Background papers
- On the Security of Succinct Interactive Arguments from Vector Commitments, https://eprint.iacr.org/2023/1737
- Learning in Pessiland via Inductive Inference, https://eccc.weizmann.ac.il/report/2023/100/
- Verifiable Quantum Advantage without Structure, https://eprint.iacr.org/2022/434.pdf
Practical information
- General public
- Free