The Polynomial Method and Variations 

Madhu Sudan (Harvard)

The polynomial method in combinatorics has recently emerged as a simple but strikingly powerful method to answer many fundamental questions about combinatorial parameters associated with geometric objects. I will survey some of the old and new applications of this method (focussing on the simpler proofs!) including:

1) "List-decoding bounds for Reed-Solomon codes": Given $n$ points in the plance, how many polynomials of degree $d$ can pass through $t$ of them? (Guruswami and S. '98)
2) "Bounds on Kakeya and Nikodym sets": How small can a subset of $F_q^n$ (the $n$-dimensional vector space over the finite field of cardinality $q$) be so that it contains a line in every direction. (Dvir 2008)
3) "Bounds on Joints in R^3": What is the largest number of "joints" (non-coplanar intersection of three lines) that can be formed by a set of L lines? (Guth and Katz, 2008)
4) "Bound on capsets in F_3^n": How large can a subset in F_3^n so that it contains no complete line? (Ellenberg, Gijswijt; based on Croot-Lev-Pach 2016).