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)|
|Number of pages||11|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|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