Low-degree testing over small fields
Let F_q be the field with q elements. We will consider the
task of testing if a m-variate function f over F_q is close
to being a polynomial of degree at most d. This task was originally
considered in the setting where d was small compared to q and
the resulting analyses found many applications in probabilistic
checking of proofs. In this talk I will describe more recent results
where we consider the setting where d > q. The natural test would
be to pick a random subspace of dimension roughly d/q and see if the
f restricted to this subspace is a polynomial of degree d. Earlier
analyses had shown that this natural test rejects functions that
are, say 1%, far from being a degree d polynomial, with probability
at least q^{-d/q}. In this talk I will describe our improved analyses
which show that this same test rejects such functions with constant
probability for constant q. Time permitting I might also mention
some applications where the setting of d > q is useful.
Based on joint works with Arnab Bhattacharyya, Elad Haramaty,
Swastik Kopparty, Noga Ron-Zewi, Grant Schoenebeck, Amir Shpilka,
and David Zuckerman.