Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. On Parallel Repetition of PCPs
 
conference paper

On Parallel Repetition of PCPs

Chiesa, Alessandro  
•
Guan, Ziyi  
•
Yildiz, Burcu  
Guruswami, Venkatesan
January 1, 2024
Leibniz International Proceedings in Informatics, LIPIcs
15 Innovations in Theoretical Computer Science Conference

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.4230/LIPIcs.ITCS.2024.34
Scopus ID

2-s2.0-85184145325

Author(s)
Chiesa, Alessandro  

École Polytechnique Fédérale de Lausanne

Guan, Ziyi  

École Polytechnique Fédérale de Lausanne

Yildiz, Burcu  

École Polytechnique Fédérale de Lausanne

Editors
Guruswami, Venkatesan
Date Issued

2024-01-01

Publisher

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Published in
Leibniz International Proceedings in Informatics, LIPIcs
ISBN of the book

9783959773096

Book part number

287

Article Number

34

Subjects

parallel repetition

•

probabilistically checkable proofs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
COMPSEC  
Event nameEvent acronymEvent placeEvent date
15 Innovations in Theoretical Computer Science Conference

Berkeley, United States

2024-01-30 - 2024-02-02

FunderFunding(s)Grant NumberGrant URL

Ethereum Foundation

Available on Infoscience
January 26, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/244808
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés