Paper 2023/1714

On Parallel Repetition of PCPs

Alessandro Chiesa, École Polytechnique Fédérale de Lausanne
Ziyi Guan, École Polytechnique Fédérale de Lausanne
Burcu Yıldız, École Polytechnique Fédérale de Lausanne

Parallel repetition refers to a set of valuable techniques used to reduce soundness error of probabilistic proofs while saving on certain efficiency measures. Parallel repetition has been studied for interactive proofs (IPs) and multi-prover interactive proofs (MIPs). In this paper we initiate the study of parallel repetition for probabilistically checkable proofs (PCPs). We show that, perhaps surprisingly, parallel repetition of a PCP can increase soundness error, in fact bringing the soundness error to one as the number of repetitions tends to infinity. This "failure" of parallel repetition is common: we find that it occurs for a wide class of natural PCPs for NP-complete languages. We explain this unexpected phenomenon by providing a characterization result: the parallel repetition of a PCP brings the soundness error to zero if and only if a certain "MIP projection" of the PCP has soundness error strictly less than one. We show that our characterization is tight via a suitable example. Moreover, for those cases where parallel repetition of a PCP does bring the soundness error to zero, the aforementioned connection to MIPs offers preliminary results on the rate of decay of the soundness error. Finally, we propose a simple variant of parallel repetition, called consistent parallel repetition (CPR), which has the same randomness complexity and query complexity as the plain variant of parallel repetition. We show that CPR brings the soundness error to zero for every PCP (with non-trivial soundness error). In fact, we show that CPR decreases the soundness error at an exponential rate in the repetition parameter.

Available format(s)
Publication info
Published elsewhere. Major revision. ITCS 2024
probabilistically checkable proofsparallel repetition
Contact author(s)
alessandro chiesa @ epfl ch
ziyi guan @ epfl ch
burcu yildiz @ epfl ch
2023-11-24: revised
2023-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alessandro Chiesa and Ziyi Guan and Burcu Yıldız},
      title = {On Parallel Repetition of {PCPs}},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1714},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.