COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |
University of Cambridge > Talks.cam > Algorithms and Complexity Seminar > On Parallel Repetition of PCPs
On Parallel Repetition of PCPsAdd to your list(s) Download to your calendar using vCal
If you have a question about this talk, please contact Tom Gur. 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. This talk is part of the Algorithms and Complexity Seminar series. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsType the title of a new list here International Cafe Scientifique Education and the State: The State of EducationOther talksM-estimation, noisy optimization and user-level local privacy Title TBC Atoms Interlinked by Light: Programmable Interactions and Entanglement High-performance Computing to Support Wind Energy Research ‘Living Standards in Angola, 1760-1975’ |