Fetching the paper…
Reading the bibliography…
We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins.
Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes
L. Babai and S. Moran · 1988
Earlier work this paper cites.
Are there interactive protocols for co-NP languages?
L. Fortnow and M. Sipser · 1988
Earlier work this paper cites.
On completeness and soundness in interactive proof systems
M. Furer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos · 1989
Earlier work this paper cites.
Private coins versus public coins in interactive proof systems
S. Goldwasser and M. Sipser · 1989
Earlier work this paper cites.
Nondeterministic exponential time has two-prover interactive protocols
L. Babai, L. Fortnow, and C. Lund · 1991
Earlier work this paper cites.
A parallel repetition theorem
R. Raz · 1995
Earlier work this paper cites.
Szemerédi’s regularity lemma and its applications in graph theory
J. Komlós and M. Simonovits · 1996
Earlier work this paper cites.
Proof verification and the hardness of approximation problems
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy · 1998
Earlier work this paper cites.
Probabilistic checking of proofs: a new characterization of NP
S. Arora and S. Safra · 1998
Earlier work this paper cites.
Property testing and its connection to learning and approximation
O. Goldreich, S. Goldwasser, and D. Ron · 1998
Earlier work this paper cites.
Complexity of k-SAT
R. Impagliazzo and R. Paturi · 1999
Earlier work this paper cites.
Time-space tradeoffs for SAT on nonuniform machines
I. Tourlakis · 2001
Earlier work this paper cites.
Quantum NP - a survey
D. Aharonov and T. Naveh · 2002
Cited alongside, same era.
Random sampling and approximation of MAX-CSPs
N. Alon, W. F. de la Vega, R. Kannan, and M. Karpinski · 2002
Cited alongside, same era.
Error reduction by parallel repetition - a negative result
U. Feige and O. Verbitsky · 2002
Cited alongside, same era.
Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?
H. Kobayashi, K. Matsumoto, and T. Yamakami · 2003
Cited alongside, same era.
Playing large games using simple strategies
R. J. Lipton, E. Markakis, and A. Mehta · 2003
Cited alongside, same era.
All languages in NP have very short quantum proofs
H. Blier and A. Tapp · 2007
Cited alongside, same era.
How hard is it to approximate the best Nash equilibrium?
E. Hazan and R. Krauthgamer · 2009
Later among the works it cites.
Parallel repetition: simplification and the no-signaling case
T. Holenstein · 2009
Later among the works it cites.
Short multi-prover quantum proofs for SAT without entangled measurements
J. Chen and A. Drucker · 2010
Later among the works it cites.
Testing product states, quantum Merlin-Arthur games and tensor optimisation
A. Harrow and A. Montanaro · 2010
Later among the works it cites.
Derandomized parallel repetition theorems for free games
R. Shaltiel · 2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The PCP theorem by gap amplification
I. Dinur · 2007
Cited alongside, same era.
S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor · 2008
Cited alongside, same era.
Algebrization: a new barrier in complexity theory
S. Aaronson and A. Wigderson · 2008
Cited alongside, same era.
Two-query PCP with subconstant error
D. Moshkovitz and R. Raz · 2008
Cited alongside, same era.
Parallel repetition in projection games and a concentration bound
A. Rao · 2008
Cited alongside, same era.
Strong parallel repetition theorem for free projection games
B. Barak, A. Rao, R. Raz, R. Rosen, and R. Shaltiel · 2009
Cited alongside, same era.
S. Aaronson and A. Ambainis · 2011
Later among the works it cites.
Subsampling mathematical programs and average-case complexity
B. Barak, M. Hardt, T. Holenstein, and D. Steurer · 2011
Later among the works it cites.
A quasipolynomial-time algorithm for the quantum separability problem
F. Brandão, M. Christandl, and J. Yard · 2011
Later among the works it cites.
Hypercontractivity, sum-of-squares proofs, and their applications
B. Barak, F. Brandão, A. Harrow, J. Kelner, D. Steurer, and Y. Zhou · 2012
Later among the works it cites.
A multi-prover interactive proof for NEXP sound against entangled provers
T. Ito and T. Vidick · 2012
Later among the works it cites.
Quantum de Finetti theorems under local measurements with applications
F. Brandão and A. Harrow · 2013
Later among the works it cites.
Three-player entangled XOR games are NP-hard to approximate
T. Vidick · 2013
Later among the works it cites.