Improved low-degree testing and its applications

Sanjeev Arora, Madhu Sudan

Research output: Contribution to journalConference articlepeer-review

94 Scopus citations


A test proposed by Rubinfield and Sudan is studied where the strongest previously known connection states that a function passes the test with probability δ for some δ>7/8 if the function has agreement ≈δ with a polynomial of degree d. A strong analysis which shows that the preceding statement is true for δ≪0.5 is presented. The analysis uses a version of Hilbert irreducibility, a tool used in the factoring of multivariate polynomials. One of the consequences of this study was a self tester/corrector for any buggy program that (supposedly) computes a polynomial over a finite field.

Original languageEnglish (US)
Pages (from-to)485-495
Number of pages11
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 1997
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Improved low-degree testing and its applications'. Together they form a unique fingerprint.

Cite this