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: Hasse derivatives and properties. Multiplicity Schwartz-Zippel lemma. Improved bounds for Kakeya sets via multiplicities.
-
Lectures 09/10: Razborov-Smolensky's lower bound for constant depth Boolean circuits with parity gates.
-
Lectures 11/12: Faster all pairs shortest paths in graphs via Razborov-Smolensky.
-
Lectures 13/14: Matrix Rigidity and upper bounds on the rigidity of certain matrices (Alman-Williams, Dvir-Edelman).
Tentative content
-
Algorithms for noisy polynomial interpolation (Sudan, Guruswami-Sudan, von zur Gathen-Shparlinski)
-
Coppersmith's algorithm for small roots of univariates modulo composites
-
Razborov-Smolensky's theorem and fast algorithms for All Pairs Shortest Path (APSP) in a graph
-
Matrix Rigidity and upper bounds on the rigidity of certain matrices (Alman-Williams, Dvir-Edelman)
-
The Polischuk-Spielman lemma, variations and applications
-
Algorithms for primality testing
-
Weil bounds - Stepanov's proofs
-
Rational approximation of algebraic numbers (Thue-Siegel-Roth theorem)
-
Interlacing polynomials and applications
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.