Fetching the paper…
Reading the bibliography…
We consider one-round games between a classical verifier and two provers who share entanglement.
Can quantum-mechanical description of physical reality be considered complete?
A. Einstein, P. Podolsky, and N. Rosen · 1935
Earlier work this paper cites.
On the Einstein-Podolsky-Rosen paradox
J. S. Bell · 1964
Earlier work this paper cites.
Proposed experiment to test local hidden-variable theories
J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt · 1969
Earlier work this paper cites.
Quantum generalizations of Bell’s inequality
B. S. Cirel’son · 1980
Earlier work this paper cites.
Two-prover one-round proof systems: Their power and their problems
U. Feige and L. Lovász · 1992
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
M. X. Goemans and D. P. Williamson · 1995
Earlier work this paper cites.
Semidefinite programming
L. Vandenberghe and S. Boyd · 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.
A threshold of ln n \ln n for approximating set cover
U. Feige · 1998
Earlier work this paper cites.
A parallel repetition theorem
R. Raz · 1998
Earlier work this paper cites.
Clique is hard to approximate within n 1 − ε n^{1-\varepsilon}
J. Håstad · 1999
Earlier work this paper cites.
Quantum Computation and Quantum Information
M. A. Nielsen and I. L. Chuang · 2000
Earlier work this paper cites.
Some optimal inapproximability results
J. Håstad · 2001
Earlier work this paper cites.
Bell inequalities and entanglement
R. F. Werner and M. M. Wolf · 2001
Cited alongside, same era.
On the power of unique 2-prover 1-round games
S. Khot · 2002
Cited alongside, same era.
Causality and Cirel’son bounds, 2004
H. Buhrman and S. Massar · 2004
Cited alongside, same era.
Convex optimization
S. Boyd and L. Vandenberghe · 2004
Cited alongside, same era.
Consequences and limits of nonlocal strategies
R. Cleve, P. Høyer, B. Toner, and J. Watrous · 2004
Cited alongside, same era.
On the hardness of approximating minimum vertex cover
I. Dinur and S. Safra · 2005
Cited alongside, same era.
Parallel repetition: simplifications and the no-signaling case
T. Holenstein · 2007
Closest in time.
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell · 2007
Closest in time.
Product rules in semidefinite programming
R. Mittal and M. Szegedy · 2007
Closest in time.
Bounding the set of quantum correlations
M. Navascues, S. Pironio, and A. Acín · 2007
Closest in time.
Unique games on expanding constraint graphs are easy
S. Arora, S. Khot, A. Kolla, D. Steurer, M. Tulsiani, and N. Vishnoi · 2008
Closest in time.
Rounding parallel repetitions of unique games
B. Barak, M. Hardt, I. Haviv, A. Rao, O. Regev, and D. Steurer · 2008
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l 1 l_{\mbox{1}}
S. Khot and N. K. Vishnoi · 2005
Cited alongside, same era.
Extremal quantum correlations for N N parties with two dichotomic observables per site, 2005
L. Masanes · 2005
Cited alongside, same era.
On the hardness of approximating multicut and sparsest-cut
S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar · 2006
Cited alongside, same era.
Near-optimal algorithms for unique games
M. Charikar, K. Makarychev, and Y. Makarychev · 2006
Cited alongside, same era.
How to play unique games using embeddings
E. Chlamtac, K. Makarychev, and Y. Makarychev · 2006
Cited alongside, same era.
Conditional hardness for approximate coloring
I. Dinur, E. Mossel, and O. Regev · 2006
Cited alongside, same era.
J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner, and T. Vidick · 2008
Closest in time.
Vertex cover might be hard to approximate to within 2 − ε 2-\varepsilon
S. Khot and O. Regev · 2008
Closest in time.
Unbounded violation of tripartite Bell inequalities
D. Perez-Garcia, M. Wolf, C. Palazuelos, I. Villanueva, and M. Junge · 2008
Closest in time.
Parallel repetition in projection games and a concentration bound
A. Rao · 2008
Closest in time.
A counterexample to strong parallel repetition
R. Raz · 2008
Closest in time.
Approximation algorithms for unique games
L. Trevisan · 2008
Closest in time.
Oracularization and two-prover one-round interactive proofs against nonlocal strategies
T. Ito, H. Kobayashi, and K. Matsumoto · 2009
Closest in time.
How to play unique games on expanders, 2009
K. Makarychev and Y. Makarychev · 2009
Closest in time.