Polynomials and applications
Time: Wednesdays, 1130-1300 and Fridays, 0930-1100
Place: Online, as of now. YouTube playlist.
Lecture notes/transcripts
2022-03-09. Batson-Spielman-Srivastava sparsifier: analysis. [Transcript, including material from previous lectures].
2022-03-04. Batson-Spielman-Srivastava sparsifier. The Calculus of Rank-1 updates. [Transcript, including material from following lectures]
2022-03-02. Recap of the proof of existence of infinite families of Ramanujan graphs of all degrees.
2022-02-25. Real-rootedness of mixed characteristic polynomials. [Transcript, including material from the previous class]
2022-02-23. Interlacing (contd.). [Transcript, including material from the previous class]. Mixed characteristic polynomials. [Transcript, including material from the following class]
2022-02-18. [Transcript, including material from the following class]. Interlacing.
2022-02-16. [Transcript]. Marcus-Spielman-Srivastava proof of existence of bipartite Ramanujan graphs of all degrees. Bilu-Linial 2-lifts.
2022-02-11. [Transcript, including the previous lecture]. Log-concavity of the coefficients of the matching polynomial. Bounds on the roots of the matching polynomial.
2022-02-09. [Transcript, updated with the following lecture]. Kirchhoff’s matrix tree theorem and the real stability of the spanning tree polynomial. The multi-affine part operation and the real stability of the matching polynomial.
2022-02-04. [Transcript, part 1]. [Transcript, part2]. Gurvits’s proof of van der Waerden conjecture (without the strict inequality part). The spanning tree polynomials. Determinant of linear sums of PSD matrices.
2022-02-02. [Transcript, updated with the following lecture] Real stability. Examples of operations preserving real stability. Gurvits’s proof of van der Waerden conjecture (without the strict inequality part).
2022-01-28. [Transcript] Introduction. Real-rooted polynomials. Gauss-Lucas lemma. Ultra log-concavity.
Brief description
This will be a “short” (a total of 18-20 hours of lectures over the semester) 2-credit course.
Tentative list of topics
Tools for analyzing the locations of roots of polynomials: rule of signs, Rolle’s theorem, Gauss- Lucas lemma.
Stability theory of polynomials, and closure properties of stable polynomials.
Connections between stability and computer science: negative association. The method of interlacing polynomials, and its use in the Marcus-Spielman-Srivastava Ramanujan graph construction.
Polynomial interpolation with errors, and a brief review of its applications in computer science, including quantum computation.
Prerequisites
The prerequisites for the course are minimal (basic calculus/analysis and Class 12 level complex numbers). Having taken one of the two Mathematical Foundations courses offered by the department would be helpful.
Evaluation
Evaluation will be based on 2-3 homework assignments (60-70% of the final grade) and a final exam (30-40% of the final grade).