On parallel repetition of PCPs

DOI10.4230/LIPICS.ITCS.2024.34MaRDI QIDQ6906402zbMATH OpenFDO

Authors Alessandro Chiesa, Ziyi Guan, Burcu Yıldız

Publication date 4 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2024.34

zbMATH Keywords

parallel repetitionprobabilistically checkable proofs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A counterexample to strong parallel repetition
• A threshold of ln n for approximating set cover
• Derandomized parallel repetition via structured PCPs
• Error reduction by parallel repetition - a negative result
• Exponentially small soundness for the direct product Z-test
• scientific article; zbMATH DE number 5485476 (Why is no real title available?)
• scientific article; zbMATH DE number 1263221 (Why is no real title available?)
• Modern cryptography, probabilistic proofs and pseudo-randomness
• New direct-product testers and 2-query PCPs
• Parallel repetition in projection games and a concentration bound
• Strong Parallel Repetition Theorem for Free Projection Games
• Towards the parallel repetition conjecture

Cited in

(1)

• On approximate reconfigurability of label cover

This page was built for publication: On parallel repetition of PCPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906402)