Parallel Repetition of Two-Prover One-Round Games: An Exposition
DOI10.4036/iis.2015.L.01zbMath1484.68063OpenAlexW2176557215MaRDI QIDQ5135260
Publication date: 19 November 2020
Published in: Interdisciplinary Information Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4036/iis.2015.l.01
Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- Perfect parallel repetition theorem for quantum XOR proof systems
- Ramanujan graphs
- On games of incomplete information
- Towards the parallel repetition conjecture
- Fully parallelized multi-prover protocols for NEXP-time
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- A one-round, two-prover, zero-knowledge protocol for NP
- A parallel repetition theorem for entangled projection games
- How to Compress Interactive Communication
- Graph expansion and the unique games conjecture
- A Counterexample to Strong Parallel Repetition
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Parallel Repetition in Projection Games and a Concentration Bound
- ECONOMICAL TORIC SPINES VIA CHEEGER'S INEQUALITY
- On the power of unique 2-prover 1-round games
- Two-query PCP with subconstant error
- Improved Rounding for Parallel Repeated Unique Games
- Strong Parallel Repetition Theorem for Free Projection Games
- Probabilistic checking of proofs
- Algebraic methods for interactive proof systems
- IP = PSPACE
- On the hardness of approximating minimization problems
- Interactive proofs and the hardness of approximating cliques
- A Parallel Repetition Theorem
- Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
- Composition of Low-Error 2-Query PCPs Using Decodable PCPs
- Analytical approach to parallel repetition
- Computational Complexity
- Parallel repetition of entangled games
- Some optimal inapproximability results
This page was built for publication: Parallel Repetition of Two-Prover One-Round Games: An Exposition
