Technical Report PHD-2014-13

TR#:PHD-2014-13
Class:PHD
Title: Polynomial Testing and Related Questions
Authors: Elad Haramaty
Supervisors: Amir Shpilka
PDFPHD-2014-13.pdf
Abstract: We consider the problem of testing if a given an n variate function f over the finite field F 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 = t(q,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 q^(2t) queries. It is also known 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. Bhattacharyya et al. (FOCS 10) gave an optimal analysis of this test for the case of the binary field and showed that the natural test actually rejects functions that were constant far from degree d-polynomials with constant probability.

In this work we extend this result for all fields showing that the natural test does indeed 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 (matches known lower bounds) 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2014/PHD/PHD-2014-13), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2014
To the main CS technical reports page

Computer science department, Technion
admin