**Date & Time:** Wednesday, January 14, 2015, 14:15-15:45.

**Venue:** Ramanujan Hall

**Title:** Low-Degree Testing

**Speaker: ** Madhu Sudan, MSR-NE

**Abstract:** 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.