Low-Degree Testing
Madhu Sudan (Microsoft)
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.