Polynomial Methods (Fall 2024)
General information
Instructor : Mrinal Kumar
Email : first name DOT last name AT tifr DOT res DOT in
Time : 2-3:30 and 4-5:30 on Wednesdays
Location : A201
Office hours : Tuesday 9:30 AM-10:30 AM in A230
Course description
The aim of this course is to discuss a collection of results in Computer Science and Math that are based on proof techniques that are loosely referred to as the polynomial method. As we shall see in the course, this can mean a few different things, but the unifying
feature of the proofs is the crucial and often surprising roles that polynomials play in these proofs.
The grades will be based on some problem sets (50%), class participation (10%) and a project that involves reading and understanding some papers, thinking about some related problems and giving a talk towards the end of the semester (40%).
Please note that this course will not be available for qualifying exams.
Problem sets
Lectures
-
Lectures 01/02: Administrative things. Joints problem. Combinatorial Nullstellansatz and applications to Chevalley-Warning.
-
Lectures 03/04: Cauchy-Davenport theorem, Erdos-Heilbronn conjecture. 3AP free sets over F_3^n.
-
Lectures 05/06: Slice rank of diagonal tensors. Kakeya and Nikodym sets over finite fields. Hasse derivatives and properties.
-
Lectures 07/08: Improved bounds for Kakeya sets via multiplicities. Razborov-Smolensky's lower bound for constant depth Boolean circuits with parity gates.
-
Lectures 09/10: Faster all pairs shortest paths in graphs via Razborov-Smolensky.
-
Lectures 11/12: Matrix Rigidity and upper bounds on the rigidity of certain matrices (Alman-Williams, Dvir-Edelman).
-
Lectures 13/14: Coppersmith's algorithm for small roots of univariates modulo composites.
-
Lectures 15/16: Algorithms for noisy polynomial interpolation (Berlekamp-Welch, Sudan, Guruswami-Sudan).
-
Lectures 17/18: The Polischuk-Spielman lemma, variations and applications.
-
Lectures 19/20: Weil bounds - Stepanov's and Bombieri's proofs of some of the special cases.
-
Lectures 21/22: Rational approximation of algebraic numbers - Thue's theorem.
-
Lectures 23/24: Interlacing polynomials and applications to bipartite Ramanujan graphs.
Things that we should have covered, but did not
-
Many other applications of the polynomial method in combinatorics.
-
Algorithms for primality testing.
-
Roth's version of the Thue-Siegel-Roth theorem. And other applications in number theory.
-
Polynomial method in pseudorandomness.
-
Other applications of Interlacing polynomials.
-
An algorithm of von zur Gathen and Shparlinksi for noisy polynomial interpolation in the setting of multiplicative errors.
References
There is no textbook for the course, but we will frequently refer to a few sources in addition to the original papers. There is a copy in the library of the book by Guth mentioned below.