# 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 20-25 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).