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.
|Jan 26||Course logistics + an invitation to SOS for computer scientists (approximating MaxCut and the Goemans-Williamson relaxation through the lens of SOS)
|Jan 28||History I: theorems about certificates, Hilbert's results and 17th problem, Motzkin's polynomial, Artin's theorem and other results on global SOS proofs
|Jan 31||History II: The "Positivstellensatz" results of Krivine, Stengle, Schmudgen, Putinar, and other variations for SOS proofs with constraints
|Feb 2||Lasserre and Parrilo formulations of bounded degree SOS optimization as a semidefinite program + Goemans-Williamson revisited
|Feb 7||Introduction to the "proofs to algorithms" technique + Planted sparse vector I|
|Feb 9||Planted sparse vector II|
|Feb 14||The "method of pseudomoments" + Tensor decomposition I|
|Feb 16||Tensor decomposition II|
|Feb 21||Robust mean estimation I: background, multi-dimensional medians, and the Lugosi-Mendelson estimator construction|
|Feb 23||Robust mean estimation II: Hopkins' sum-of-squares algorithm|
|Feb 28||First lower bounds: Grigoriev-Laurent lower bound for knapsack/parity|
|Mar 2||Knapsack/parity lower bound II|
|Mar 7||Grigoriev-Schoenebeck lower bound for 3-XOR-SAT|
|Mar 9||3-XOR-SAT lower bound II|
|Mar 14||Planted clique lower bound I: problem setting, basic algorithms, Feige-Krauthgamer degree 2 lower bound|
|Mar 16||Planted clique lower bound II: Feige-Krauthgamer moments, Kelner's polynomial, and the pseudocalibration relation|
|Mar 21||Spring Break|
|Mar 23||Spring Break|
|Mar 28||Planted clique lower bound III: deriving calibrated pseudomoments, truncation|
|Mar 30||Planted clique lower bound IV: fixing pseudocalibration and concentration results for constraints|
|Apr 4||Planted clique lower bound V: introduction to graphical matrices|
|Apr 6||Planted clique lower bound VI: canonical factorization and sketch of positivity proof strategy|
|Apr 11||Planted clique lower bound VII: wrapping up details of canonical factorization and last positivity proof ideas|
|Apr 13||Pseudocalibration to low-degree polynomial algorithms I|
|Apr 18||Pseudocalibration to low-degree polynomial algorithms II: low-degree predictions in general Bernoulli models and the overlap parameter|
|Apr 20||Pseudocalibration to spectral algorithms I|
|Apr 25||Pseudocalibration to spectral algorithms II|
|Apr 27||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.)
|Assigned||Due||Link and Details|
|Feb 12||Mar 4|
|Mar 14||Apr 4|
|Apr 10||May 6|
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