Fetching the paper…
Reading the bibliography…
Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as $\mathsf{MIP} = \mathsf{NEXP}$ [BFL91] and the PCP theorem [AS98,ALM+98].
Probabilistic algorithms for sparse polynomials
Richard Zippel · 1979
Earlier work this paper cites.
Fast probabilistic algorithms for verification of polynomial identities
Jacob Schwartz · 1980
Earlier work this paper cites.
Simple unified form for the major no-hidden-variables theorems
David Mermin · 1990
Earlier work this paper cites.
Incompatible results of quantum measurements
Asher Peres · 1990
Earlier work this paper cites.
Non-deterministic exponential time has two-prover interactive protocols
László Babai, Lance Fortnow, and Carsten Lund · 1991
Earlier work this paper cites.
Self-testing/correcting with applications to numerical problems
Manuel Blum, Michael Luby, and Ronitt Rubinfeld · 1993
Earlier work this paper cites.
Low-degree tests
Katalin Friedl, Zsolt Hatsagi, and Alexander Shen · 1994
Earlier work this paper cites.
Nearly-linear size holographic proofs
Alexander Polishchuk and Daniel Spielman · 1994
Earlier work this paper cites.
Complementarity and nondegeneracy in semidefinite programming
Farid Alizadeh, Jean-Pierre Haeberly, and Michael Overton · 1997
Earlier work this paper cites.
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
Ran Raz and Shmuel Safra · 1997
Cited alongside, same era.
Proof verification and the hardness of approximation problems
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy · 1998
Cited alongside, same era.
Probabilistic checking of proofs: a new characterization of NP
Sanjeev Arora and Shmuel Safra · 1998
Cited alongside, same era.
A simple demonstration of Bell’s theorem involving two observers and no probabilities or inequalities
PK Aravind · 2002
Cited alongside, same era.
Convex Optimization
Stephen Boyd and Lieven Vandenberghe · 2004
Cited alongside, same era.
Algebraic property testing: the role of invariance
Tali Kaufman and Madhu Sudan · 2008
Cited alongside, same era.
The complexity of entangled games
Thomas Vidick · 2011
Later among the works it cites.
A multi-prover interactive proof for NEXP sound against entangled provers
Tsuyoshi Ito and Thomas Vidick · 2012
Later among the works it cites.
Three-player entangled XOR games are NP-hard to approximate
Thomas Vidick · 2016
Later among the works it cites.
On axis-parallel tests for tensor product codes
Alessandro Chiesa, Peter Manohar, and Igor Shinkar · 2017
Later among the works it cites.
Low-degree testing for quantum states, and a quantum entangled games PCP
Anand Natarajan and Thomas Vidick · 2018
Later among the works it cites.
Two-player entangled games are NP-hard
Anand Natarajan and Thomas Vidick · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Lecture 5 from 15-859(M): Randomized Algorithms
Avrim Blum · 2011
Cited alongside, same era.
Parallel repetition of entangled games
Julia Kempe and Thomas Vidick · 2011
Cited alongside, same era.
Guest column: testing linear properties: some general theme
Madhu Sudan · 2011
Cited alongside, same era.
𝖭𝖤𝖤𝖷𝖯 ⊆ 𝖬𝖨𝖯 ∗ \mathsf{NEEXP}\subseteq\mathsf{MIP}^{*}
Anand Natarajan and John Wright · 2019
Later among the works it cites.
𝖬𝖨𝖯 ∗ = 𝖱𝖤 \mathsf{MIP}^{*}=\mathsf{RE}
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen · 2020
Closest in time.