Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PARALLEL REPETITION:
Reports tagged with Parallel Repetition:
TR07-043 | 7th May 2007
Uriel Feige, Guy Kindler, Ryan O'Donnell

Understanding Parallel Repetition Requires Understanding Foams

Motivated by the study of Parallel Repetition and also by the Unique
Games Conjecture, we investigate the value of the Odd Cycle Games''
under parallel repetition. Using tools from discrete harmonic
analysis, we show that after $d$ rounds on the cycle of length $m$,
the value of the game is ... more >>>

TR08-013 | 16th January 2008
Anup Rao

Parallel Repetition in Projection Games and a Concentration Bound

In a two player game, a referee asks two cooperating players (who are
not allowed to communicate) questions sampled from some distribution
and decides whether they win or not based on some predicate of the
questions and their answers. The parallel repetition of the game is
the game in which ... more >>>

TR08-018 | 28th February 2008
Ran Raz

A Counterexample to Strong Parallel Repetition

The parallel repetition theorem states that for any two-prover game,
with value $1- \epsilon$ (for, say, $\epsilon \leq 1/2$), the value of
the game repeated in parallel $n$ times is at most
$(1- \epsilon^c)^{\Omega(n/s)}$, where $s$ is the answers' length
(of the original game) and $c$ is a universal ... more >>>

TR09-027 | 2nd April 2009
Iftach Haitner

A Parallel Repetition Theorem for Any Interactive Argument

Revisions: 2

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, ... more >>>

TR09-109 | 3rd November 2009
Kai-Min Chung, Feng-Hao Liu

Tight Parallel Repetition Theorems for Public-coin Arguments

Following Hastad, Pass, Pietrzak, and Wikstrom (2008), we study parallel repetition theorems for public-coin interactive arguments and their generalization. We obtain the following results:

1. We show that the reduction of Hastad et al. actually gives a tight direct product theorem for public-coin interactive arguments. That is, $n$-fold parallel repetition ... more >>>

TR09-120 | 18th November 2009
Charanjit Jutla

Almost Optimal Bounds for Direct Product Threshold Theorem

Revisions: 2

We consider weakly-verifiable puzzles which are challenge-response puzzles such that the responder may not
be able to verify for itself whether it answered the challenge correctly. We consider $k$-wise direct product of
such puzzles, where now the responder has to solve $k$ puzzles chosen independently in parallel.
Canetti et ... more >>>

TR10-107 | 6th July 2010
Irit Dinur, Or Meir

Derandomized Parallel Repetition via Structured PCPs

Revisions: 3

A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof, and in return is allowed to err with some bounded probability. The probability that the verifier accepts ... more >>>

TR13-179 | 15th December 2013
Irit Dinur, David Steurer

Direct Product Testing

A direct product is a function of the form $g(x_1,\ldots,x_k)=(g_1(x_1),\ldots,g_k(x_k))$. We show that the direct product property is locally testable with $2$ queries, that is, a canonical two-query test distinguishes between direct products and functions that are from direct products with constant probability.

This local testing question comes up ... more >>>

TR14-095 | 24th July 2014
Mark Braverman, Ankit Garg

Small value parallel repetition for general games

Revisions: 1

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. We use information theoretic techniques in our proof. Our proofs also extend to the high value regime (value close to 1) ... more >>>

TR14-182 | 22nd December 2014
Dana Moshkovitz

Direct Product Testing With Nearly Identical Sets

In this work we analyze a direct product test in which each of two provers receives a subset of size n of a ground set U,
and the two subsets intersect in about (1-\delta)n elements.
We show that if each of the provers provides labels to the n ... more >>>

TR15-069 | 21st April 2015
Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

On Fortification of General Games

Revisions: 1

A recent result of Moshkovitz~\cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel ... more >>>

TR16-047 | 23rd March 2016
Mohammad Bavarian, Thomas Vidick, Henry Yuen

Parallel repetition via fortification: analytic view and the quantum case

In a recent work, Moshkovitz [FOCS '14] presented a transformation on two-player games called "fortification'', and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial ... more >>>

TR16-060 | 15th April 2016
Henry Yuen

A parallel repetition theorem for all entangled games

The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Raz's classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known.
... more >>>

TR16-160 | 26th October 2016
Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

Multiplayer parallel repetition for expander games

Revisions: 1

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially ... more >>>

TR17-182 | 21st November 2017
Mark Braverman, Young Kun Ko

Information Value of Two-Prover Games

We introduce a generalization of the standard framework for studying the difficulty of two-prover games. Specifically, we study the model where Alice and Bob are allowed to communicate (with information constraints) --- in contrast to the usual two-prover game where they are not allowed to communicate after receiving their respective ... more >>>

TR18-034 | 15th February 2018
Young Kun Ko

On Symmetric Parallel Repetition : Towards Equivalence of MAX-CUT and UG

Unique Games Conjecture (UGC), proposed by [Khot02], lies in the center of many inapproximability results. At the heart of UGC lies approximability of MAX-CUT, which is a special instance of Unique Game.[KhotKMO04, MosselOO05] showed that assuming Unique Games Conjecture, it is NP-hard to distinguish between MAX-CUT instance that has a ... more >>>

TR18-121 | 20th June 2018
Justin Holmgren, Lisa Yang

Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem

Non-signaling games are an important object of study in the theory of computation, for their role both in quantum information and in (classical) cryptography. In this work, we study the behavior of these games under parallel repetition.

We show that, unlike the situation both for classical games and for two-player ... more >>>

TR19-049 | 2nd April 2019

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

Revisions: 2

Parallel repetition is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols and public-coin protocols. However, it does not do so in the general case.

Haitner [FOCS '09, SiCOMP '13] presented a simple method for transforming any interactive argument $\pi$ into a slightly modified ... more >>>

TR20-120 | 12th August 2020
Justin Holmgren, Ran Raz

A Parallel Repetition Theorem for the GHZ Game

We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel $t$ times is at most $t^{-\Omega(1)}$. Previously, only a bound of $\approx \frac{1}{\alpha(t)}$, where $\alpha$ is the inverse Ackermann ... more >>>

TR20-131 | 20th August 2020
Rahul Jain, Srijita Kundu

A Direct Product Theorem for One-Way Quantum Communication

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any $\varepsilon, \zeta > 0$ and any $k\geq1$, we show that
$\mathrm{Q}^1_{1-(1-\varepsilon)^{\Omega(\zeta^6k/\log|\mathcal{Z}|)}}(f^k) = \Omega\left(k\left(\zeta^5\cdot\mathrm{Q}^1_{\varepsilon + 12\zeta}(f) - \log\log(1/\zeta)\right)\right),$
where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with ... more >>>

TR20-144 | 7th September 2020
Mohammad Jahanara, Sajin Koroth, Igor Shinkar

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is ... more >>>

TR20-173 | 18th November 2020
Kunal Mittal, Ran Raz

Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines

Revisions: 1

We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machines with advice. To the best of our knowledge, this is the first connection between parallel repetition and lower bounds for time complexity and the first ... more >>>

TR21-042 | 16th March 2021
Dana Moshkovitz

Strong Parallel Repetition for Unique Games on Small Set Expanders

We show that NP-hardness of approximating Boolean unique games on small set expanders can be amplified to the full Unique Games Conjecture on small set expanders.
The latter conjecture is known to imply hardness results for problems like Balanced-Separator, Minimum-Linear-Rearrangement and Small-Set-Expansion that are not known under the Unique ... more >>>

TR21-101 | 13th July 2021
Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

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

Revisions: 1

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the $n$-fold GHZ game is at most $n^{-\Omega(1)}$. This was first established by Holmgren and ... more >>>

TR22-039 | 14th March 2022
Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

Parallel Repetition For All 3-Player Games Over Binary Alphabet

We prove that for every 3-player (3-prover) game, with binary questions and answers and value less than $1$, the value of the $n$-fold parallel repetition of the game decays polynomially fast to $0$. That is, for every such game, there exists a constant $c>0$, such that the value of the ... more >>>

TR22-043 | 2nd April 2022
Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there ... more >>>

ISSN 1433-8092 | Imprint