Analytical approach to parallel repetition

By Irit Dinur, David Steurer. Symposium on the Theory of Computing, 2013

568 citations recorded by the source corpus.

We propose an analytical framework for studying parallel repetition, a basic product operation for one-round twoplayer games. In this framework, we consider a relaxation of the value of projection games. We show that this relaxation is multiplicative with respect to parallel repetition and that it provides a good approximation to the game value. Based on this relaxation, we prove the following improved parallel repetition bound: For every projection game G with value at most ρ, the k-fold parallel repetition G⊗k has value at most [EQUATION] This statement implies a parallel repetition bound for projection games with low value ρ. Previously, it was not known whether parallel repetition decreases the value of such games. This result allows us to show that approximating set cover to within factor (1 --- ε) ln n is NP-hard for every ε > 0, strengthening Feige's quasi-NP-hardness and also building on previous work by Moshkovitz and Raz. In this framework, we also show improved bounds for few parallel repetitions of projection games, showing that Raz's counterexample to strong parallel repetition is tight even for a small number of repetitions. Finally, we also give a short proof for the NP-hardness of label cover(1, δ) for all δ > 0, starting from the basic PCP theorem.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/d4501f8c91b9d1659ad0f4d73194d968bc5012b3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2017, background): “Cannot be efficiently approximated to (1− o(1)) lnn unless P = NP [78].”
Towards Fast Computation of Certified Robustness for ReLU Networks (2018, methodology): “Theorem A.6 ((Raz & Safra, 1997; Alon et al., 2006; Dinur & Steurer, 2014)).”