Low-Degree Testing

Madhu Sudan

Harvard University

Low-degree testing is the task of testing if a multivariate function given as a black box is (close to) a polynomial of low-degree in its input. The simplest case of this problem (for homogenous degree one polynomials) is the famed linearity testing problem of Blum, Luby and Rubinfeld, which already opened the door to a rich store of applications and tools. Extensions to higher degrees has similarly led to many applications (constructions of PCPs, small set expanders, algebraic XOR lemmas) and many tools. In this talk I will try to survey some of the flavors of this problem and reflect on some of the tools and applications.