Wed, December 28, 2016
Public Access Category: All |
||||||||||||||||||||||
|
- Time:
- 4:00pm-5:00pm
- Location:
- Ramanujan Hall
- Description:
- Speaker: Prof. Madhu Sudan (Harvard University)
Title: The Polynomial Method and Variations
Abstract:
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).