Information flow in probabilistic proofs
Event details
| Date | 23.01.2026 |
| Hour | 13:00 › 15:00 |
| Speaker | Burcu Yildiz |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Thomas Vidick
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Rüdiger Urbanke
Abstract
Probabilistic proofs enable a verifier to verify a statement, including membership in hard languages, using minimal resources, such as time or space, and minimal help, such as interaction with a prover or query to an oracle. Verifier's ability to make a correct decision, in formal terms, soundness and completeness of the probabilistic proof, despite the use of minimal resources, tells us a lot: The minimal help provided by prover(s) contains the vital information that can be utilized by the verifier to make the decision of accept or reject. Is this all, or could the proof contain more information? One way to answer this question is to investigate the zero-knowledge property of proofs, where we require the verifier to learn nothing except the decision. Another way to approach this question is to investigate the unexpected behaviours of parallel repetition of proofs. Parallel repetition of proofs has been widely studied, and previous work showed that the decay of soundness error might be worse than we intuitively expect. This fact suggests us that there is a flow of information other than the ones we expect. In this thesis, we investigate these different settings of the information flow in probabilistic proofs.
Background papers
Exam president: Prof. Thomas Vidick
Thesis advisor: Prof. Alessandro Chiesa
Co-examiner: Prof. Rüdiger Urbanke
Abstract
Probabilistic proofs enable a verifier to verify a statement, including membership in hard languages, using minimal resources, such as time or space, and minimal help, such as interaction with a prover or query to an oracle. Verifier's ability to make a correct decision, in formal terms, soundness and completeness of the probabilistic proof, despite the use of minimal resources, tells us a lot: The minimal help provided by prover(s) contains the vital information that can be utilized by the verifier to make the decision of accept or reject. Is this all, or could the proof contain more information? One way to answer this question is to investigate the zero-knowledge property of proofs, where we require the verifier to learn nothing except the decision. Another way to approach this question is to investigate the unexpected behaviours of parallel repetition of proofs. Parallel repetition of proofs has been widely studied, and previous work showed that the decay of soundness error might be worse than we intuitively expect. This fact suggests us that there is a flow of information other than the ones we expect. In this thesis, we investigate these different settings of the information flow in probabilistic proofs.
Background papers
- A Zero-Knowledge PCP Theorem, Tom Gur, Jack O'Connor, Nicholas Spooner, https://dl.acm.org/doi/pdf/10.1145/3717823.3718128
- Parallel Repetition: Simplifications and the No-Signaling Case, Thomas Holenstein, https://arxiv.org/pdf/cs/0607139
- Coding for Computing, Alon Orlitsky, James R. Roche, https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=915643&tag=1
Practical information
- General public
- Free