Ph.D Thesis
Ph.D Student Haramaty Elad Polynomial Testing and Related Questions Department of Computer Science Professor Amir Shpilka

Abstract

We consider the problem of testing if a given an n variate function f over the finite field Fq of q elements is close to degree d polynomial. The natural, low-query, test for this property would be to pick the smallest dimension t = tq,d~ d/q such that every function of degree greater than d reveals this aspect on some t-dimensional affine subspace of the space 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 showed that this natural test rejected functions that were constant far from degree d polynomials with probability at least order of q-t. Thus to get a constant probability of detecting functions that are at constant distance from the space of degree d polynomials, the tests made q2t queries. It is also known that when q is prime, then qt queries are necessary. Thus these tests were off by at least a quadratic factor from known lower bounds.

In this work we show that the natural test, in fact, rejects functions that are constant far from degree d polynomials with constant probability, where the constants depend only on q the field size. Thus our analysis thus shows that this test is optimal when q is prime.

Moreover, we extend this result to a more general notion called lifted codes. Given a base code over a t-dimensional space, its n-dimensional lift consists of all words whose restriction to every t-dimensional affine subspace is a codeword of the base code. Lifting not only captures the most familiar codes, which can be expressed as lifts of low-degree polynomials, it also yields new codes when lifting “medium-degree” polynomials whose rate is better than that of corresponding polynomial codes, and all other combinatorial qualities are no worse. We shows that the natural test for those codes also has constant rejection probability for functions that are constant far from the code.

We also study functions that pass a similar test, called Gowers Norm, with non-negligible probability. We present structural results for such polynomials with noticeable Gower norm, showing that they can be represented as "nice" function of lower degree polynomials.

We conclude this thesis with an application, showing that by using our low degree tester one can detect efficiently simple paths in graphs.