The Taub Faculty of Computer Science Events and Talks

We consider the problem of testing if a given function f is close to a n-variate degree d polynomial over the finite field of q elements. The natural, low-query, test for this property would be to pick the smallest dimension t= t(q,d )≈ d/q such that every function of degree greater than d reveals this feature on some t-dimensional affine subspace and to test that f when restricted to a random t-dimensional affine subspace is a polynomial of degree at most d on this subspace. Such a test makes only qt queries, independent of n. Previous works, by Alon et al., and Kaufman and Ron and Jutla et al. , showed that this natural test rejected functions that were Ω(1)-far from degree d-polynomials with probability at least Ω(q−t) (the results of hold for all fields, while the results of hold only for fields of prime order). Thus to get a constant probability of detecting functions that were at constant distance from the space of degree d polynomials, the tests made q^{2t} queries. Kaufman and Ron also noted that when q is prime, then q^t queries are necessary. Thus these tests were off by at least a quadratic factor from known lower bounds. It was unclear if the soundness analysis of these tests were tight and this question relates closely to the task of understanding the behavior of the Gowers Norm. This motivated the work of Bhattacharyya et al., who gave an optimal analysis for the case of the binary field and showed that the natural test actually rejects functions that were Ω(1)-far from degree d-polynomials with probability at least Ω(1).

In this work we give an optimal analysis of this test for all fields showing that the natural test does indeed reject functions that are Ω(1)-far from degree d polynomials with Ω(1)-probability. Our analysis thus shows that this test is optimal (matches known lower bounds) when q is prime. Our approach extends the proof technique of Bhattacharyya et al., however it has to overcome many technical barriers in the process. The natural extension of their analysis leads to an O(q^d) query complexity, which is worse than that of Kaufman and Ron for all q except 2! The main technical ingredient in our work is a tight analysis of the number of “hyperplanes” (affine subspaces of co-dimension 1) on which the restriction of a degree dpolynomial has degree less than d. We show that the number of such hyperplanes is at most O(qtq,d ) — which is tight to within constant factors.

Joint work with Amir Shpilka and Madhu Sudan.