![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Monday 05 February 2024, 14:00-15:00
On Parallel Repetition of PCPs
- 👤 Speaker: Ziyi Guan (EPFL)
- 📅 Date & Time: Monday 05 February 2024, 14:00 - 15:00
- 📍 Venue: Computer Laboratory, William Gates Building, FW11
Abstract
Parallel repetition has been widely used for interactive proofs (IPs) and multi-prover interactive proofs (MIPs). We initiate the systematic study of parallel repetition for probabilistically checkable proofs (PCPs).
We uncover a surprising result: canonical parallel repetition of a PCP increases soundness error and brings the limit of the soundness error to one. This failure turns out to be rather common and we characterize the cause for it. Finally we propose a simple variant of parallel repetition for PCPs that works as expected.
Based on https://eprint.iacr.org/2023/1714, joint work with Alessandro Chiesa and Burcu Yıldız.
Series This talk is part of the Algorithms and Complexity Seminar series.
Included in Lists
- Algorithms and Complexity Seminar
- All Talks (aka the CURE list)
- bld31
- Cambridge talks
- Computer Laboratory, William Gates Building, FW11
- Department of Computer Science and Technology talks and seminars
- Interested Talks
- School of Technology
- Trust & Technology Initiative - interesting events
- yk449
Note: Ex-directory lists are not shown.