Some Improvements to Total Degree Tests

Probabilistic algorithms for sparse polynomials

R. Zippel · 1979

Earlier work this paper cites.

Fast probabilistic algorithms for verification of polynomial identities

J.T. Schwartz · 1980

Earlier work this paper cites.

Self-testing/correcting with applications to numerical problems

M. Blum, M. Luby, and R. Rubinfeld · 1990

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.

Checking computations in polylogarithmic time

L. Babai, L. Fortnow, L.A. Levin, and M. Szegedy · 1991

Earlier work this paper cites.

Approximating clique is almost NP

U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy · 1991

Earlier work this paper cites.

Self-testing/correcting for polynomials and for approximate functions

P. Gemmell, R. Lipton, R. Rubinfeld, M. Sudan, and A. Wigderson · 1991

Cited alongside, same era.

Proof verification and the intractability of approximation problems

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy · 1992

Cited alongside, same era.

Probabilistic checking of proofs: A new characterization of NP

S. Arora and S. Safra · 1992

Cited alongside, same era.

Efficient Probabilistic Verification

S. Phillips and S. Safra · 1992

Cited alongside, same era.

Testing polynomial functions efficiently and over rational domains

R. Rubinfeld and M. Sudan · 1992

Cited alongside, same era.

Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems

M. Sudan · 1992

Cited alongside, same era.

Transparent (holographic) proofs

L. Babai · 1993

Later among the works it cites.

On slightly superlinear transparent proofs

L. Babai and K. Friedl · 1993

Later among the works it cites.

Efficient probabilistically checkable proofs

M. Bellare, S. Goldwasser, C. Lund, and A. Russell · 1993

Later among the works it cites.

Robust characterizations of polynomials with applications to program testing

R. Rubinfeld and M. Sudan · 1993

Later among the works it cites.

Low-degree tests

K. Friedl, Zs. Hátsági, and A. Shen · 1994

Later among the works it cites.