Improved low-degree testing and its applications

Sanjeev Arora; Madhu Sudan

doi:10.1145/258533.258642

Improved low-degree testing and its applications

Sanjeev Arora, Madhu Sudan

Research output: Contribution to journal › Conference article › peer-review

99 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	485-495
Number of pages	11
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/258533.258642
State	Published - 1997
Event	Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA Duration: May 4 1997 → May 6 1997

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/258533.258642

Cite this

@article{86a64a6b8db84740a180440bbc767d86,

title = "Improved low-degree testing and its applications",

abstract = "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.",

author = "Sanjeev Arora and Madhu Sudan",

year = "1997",

doi = "10.1145/258533.258642",

language = "English (US)",

pages = "485--495",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing ; Conference date: 04-05-1997 Through 06-05-1997",

}

TY - JOUR

T1 - Improved low-degree testing and its applications

AU - Arora, Sanjeev

AU - Sudan, Madhu

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030645273&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030645273&partnerID=8YFLogxK

U2 - 10.1145/258533.258642

DO - 10.1145/258533.258642

M3 - Conference article

AN - SCOPUS:0030645273

SN - 0734-9025

SP - 485

EP - 495

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing

Y2 - 4 May 1997 through 6 May 1997

ER -

Improved low-degree testing and its applications

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this