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).

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).

Description

Ramanujan Hall

Date

Wed, December 28, 2016

Start Time

4:00pm-5:00pm IST

Duration

1 hour

Priority

5-Medium

Access

Public

Created by

DEFAULT ADMINISTRATOR

Updated

Tue, December 27, 2016 10:56am IST