Madhu Sudan: Low-Degree Testing

Abstract:

Given a n-variate function f over the finite field F_q and a degree parameter \(d \ll q\), how fast can we estimate the correlation of f with a degree d n-variate polynomial? (Here correlation is defined to be the fraction of points where f agrees exactly with a degree d polynomial P, maximized over the choice of P.) Specifically if we allow queries to values of f at random values what is the minimum number of queries needed?

A natural estimator of this correlation is to pick a random line in (F_q)ⁿ and to use the correlation of f with the space of degree d univariate polynomials on this line as an estimate? Given a bound \(\rho\) on the desired correlation this leads to a test with complexity \(d/\textrm{poly}(\rho')\) but is this a reliable estimator of the correlation?

In this talk we will describe the long path to a final affirmative answer to this question. This question had been considered a central one in the design of “probabilisitically checkable proofs (PCPs)” and previous works had shown positive answers for a more complex test, or under the condition that \(q > d^4\). We finally resolve the question all the way down to \(q = O(d)\). The path involves intriguing connections with the Hilbert Irreducibility question for multivariate polynomials, and Newton’s method (or Hensel lifting) for finding roots of a polynomial.

Based on this  joint work with Prahladh Harsha, Mrinal Kumar and Ramprasad Saptharishi.