This course is a survey of sum-of-squares (SOS) polynomial proofs and their applications in and connections to various fields of mathematics and computer science. SOS proofs try to bound polynomial optimization problems or show that polynomial systems of equations cannot be solved by using the fact that squared polynomials are non-negative. While this may sound simple or a bit naive, in fact searching for SOS proofs has turned out to be a powerful algorithmic technique that is now ubiquitous in theoretical computer science.
The course will be organized in four parts.
Part 1: The mathematical history of algebraic proofs, including Hilbert's "Nullstellensatz" and 17th problem, classical moment problems, and more recent "Positivstellensatz" results.
Part 2: Recent developments relating SOS proofs to questions in optimization and computer science. We will see how to search for SOS proofs using semidefinite programming, and how such algorithms have yielded theoretical breakthroughs for many problems of current interest.
Part 3: Lower bounds against these algorithms, which give some of the strongest evidence we have of computational hardness, especially for high-dimensional random problems coming from combinatorial optimization, statistics, and machine learning.
Part 4: Some further results that situate SOS algorithms in the "big picture" of computation and the theory of algorithms. In particular, we might look at the efficiency of SOS and recent work seeking to make SOS-based algorithms faster, comparisons between SOS and other convex relaxations, and/or perspectives on SOS from convex geometry.
The best way to contact me is by email, at dmitriy [dot] kunisky [at] yale.edu.
Office hours will be held by appointment at least for the first two weeks, while classes are online. Email me to schedule a time to talk. We will discuss choosing a time for regular office hours at our first in-person meeting. My office is Room 337 at 17 Hillhouse Avenue (YINS, the Yale Institute for Network Science); outside office hours and appointments, you're welcome to try your luck finding me there.
Class will meet Mondays and Wednesdays, 1pm to 2:15pm. In-person classes will be held in the Watson Center (WTS), Room A68. (Please note this is not Watson Hall (AKW)!)
A few details concerning the start of the semester:
Below is a tentative schedule, to be updated as the semester progresses.
|Course logistics + an invitation to SOS for computer scientists (approximating MaxCut and the Goemans-Williamson relaxation through the lens of SOS)
|History I: theorems about certificates, Hilbert's results and 17th problem, Motzkin's polynomial, Artin's theorem and other results on global SOS proofs
|History II: The "Positivstellensatz" results of Krivine, Stengle, Schmudgen, Putinar, and other variations for SOS proofs with constraints
|Lasserre and Parrilo formulations of bounded degree SOS optimization as a semidefinite program + Goemans-Williamson revisited
|Introduction to the "proofs to algorithms" technique + Planted sparse vector I
|Planted sparse vector II
|The "method of pseudomoments" + Tensor decomposition I
|Tensor decomposition II
|Robust mean estimation I: background, multi-dimensional medians, and the Lugosi-Mendelson estimator construction
|Robust mean estimation II: Hopkins' sum-of-squares algorithm
|First lower bounds: Grigoriev-Laurent lower bound for knapsack/parity
|Knapsack/parity lower bound II
|Grigoriev-Schoenebeck lower bound for 3-XOR-SAT
|3-XOR-SAT lower bound II
|Planted clique lower bound I: problem setting, basic algorithms, Feige-Krauthgamer degree 2 lower bound
|Planted clique lower bound II: Feige-Krauthgamer moments, Kelner's polynomial, and the pseudocalibration relation
|Planted clique lower bound III: deriving calibrated pseudomoments, truncation
|Planted clique lower bound IV: fixing pseudocalibration and concentration results for constraints
|Planted clique lower bound V: introduction to graphical matrices
|Planted clique lower bound VI: canonical factorization and sketch of positivity proof strategy
|Planted clique lower bound VII: wrapping up details of canonical factorization and last positivity proof ideas
|Pseudocalibration to low-degree polynomial algorithms I
|Pseudocalibration to low-degree polynomial algorithms II: low-degree predictions in general Bernoulli models and the overlap parameter
|Pseudocalibration to spectral algorithms I
|Pseudocalibration to spectral algorithms II
|Student project presentations
You do not need to buy any books for this course. You can find the lecture notes here. I will try to make these as thorough as possible and to update them with each lecture's materials, probably with more elaboration than we have time for in class. In particular, the bibliography and list of open problems in the notes is a great place to look for project topics, in addition to the list below.
Homework will be posted here, and is to be submitted to me by email, in PDF format produced with LaTeX, by the due date indicated. Please try to talk to me in advance if you need more time for an assignment. You do not need to solve all exercises in the notes—only those posted here. (But you are welcome to solve more, and might find it helps you internalize the material.)
|Link and Details
Most of your grade will be based on a final project, for which I would like you to read a substantial research paper, work on an open theoretical problem, or run an interesting numerical experiment, and make a short oral presentation and written report about what you find. You do not need to make a new discovery to get a good grade; I do, however, expect you to engage seriously with your topic—if you read a paper then try to present it in the most digestible way possible (even if that is different from what the authors wrote), if you work on a problem and get stuck then tell us what you think makes it difficult to make progress, and so forth.
Here are some possible topics and associated references, roughly grouped by theme. Any open problem or substantial reference from the notes will also work. I would also be glad to hear about further ideas that you've seen in the literature or where you think SOS might be relevant to your research (if you are doing other independent work). Email me if you have suggestions!
SOS Algorithms and Lower Bounds
Real(ish) Applications of SOS
This survey by Georgina Hall is a great starting point to look for more references about applications.
SOS as a Proof Assistant
Geometric and Algebraic Aspects of SOS