Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic colloquium on computational complexity

A Tight Parallel-Repetition Theorem for Random-Terminating Interactive Arguments.

Itay Berman, Iftach Haitner, Eliad Tsfadia

Published Jan 1, 2019• 1 citation
OpenAlex

Related papers

Guest column: parallel repetition theorems for interactive arguments

Kai-Min Chung, Rafael Pass

We survey recent results on parallel repetition theorems for computationally-sound interactive proofs (a.k.a. interactive arguments).

ACM SIGACT News•Mar 6, 2013•1 citation

An Efficient Parallel Repetition Theorem

Johan Håstad, Rafael Pass, Douglas Wikström +1 more

Lecture notes in computer science•Jan 1, 2010•46 citations

On Parallel Repetition of Interactive Proof Systems

Oded Goldreich

Lecture notes in computer science•Jan 1, 2025•1 citation

A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof.

Uma Girish, Justin Holmgren, Kunal Mittal +2 more

Electronic colloquium on computational complexity•Jan 1, 2021•0 citations

Tight Post-Quantum Parallel Repetition for Private-Coin Arguments

Zvika Brakerski, Andrew Huang, Yael Tauman Kalai +1 more

We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness error at a tight exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, where the parallel repeated verifier accepts if and only if at least $t$ of the executions are accepted (for some threshold $t$). Prior to this work, these results were known only when the cheating prover was assumed to be classical, and it was not known how to achieve tight bounds. As a corollary, we construct the first constant-round succinct argument for $\mathsf{QMA}$ with negligible completeness and soundness errors assuming only the existence of quantum homomorphic encryption.

quant-pharXiv:2609.38941•Oct 1, 2026•0 citations

Strong Parallel Repetition Theorem for Free Projection Games

Boaz Barak, Anup Rao, Ran Raz +2 more

Lecture notes in computer science•Jan 1, 2009•28 citations
We show that assuming the existence of homomorphic encryption, parallel repetition of all interactive arguments (after being run under homomorphic encryption) reduces the soundness error at a tight exponential rate even in the post-quantum setting. Moreover, we generalize this result to hold for threshold verifiers, where the parallel repeated verifier accepts if and only if at least ttt of the executions are accepted (for some threshold ttt). Prior to this work, these results were known only when the cheating prover was assumed to be classical, and it was not known how to achieve tight bounds. As a corollary, we construct the first constant-round succinct argument for QMA\mathsf{QMA}QMA with negligible completeness and soundness errors assuming only the existence of quantum homomorphic encryption.