This course is a survey of sumofsquares (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 nonnegative. 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 highdimensional 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 SOSbased 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 inperson 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. Inperson 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.
Date  Details 

Week 1  
Jan 26  Course logistics + an invitation to SOS for computer scientists (approximating MaxCut and the GoemansWilliamson 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

Week 2  
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 + GoemansWilliamson revisited

Week 3  
Feb 7  Introduction to the "proofs to algorithms" technique + Planted sparse vector I 
Feb 9  Planted sparse vector II 
Week 4  
Feb 14  The "method of pseudomoments" + Tensor decomposition I 
Feb 16  Tensor decomposition II 
Week 5  
Feb 21  Robust mean estimation I: background, multidimensional medians, and the LugosiMendelson estimator construction 
Feb 23  Robust mean estimation II: Hopkins' sumofsquares algorithm 
Week 6  
Feb 28  First lower bounds: GrigorievLaurent lower bound for knapsack/parity 
Mar 2  Knapsack/parity lower bound II 
Week 7  
Mar 7  GrigorievSchoenebeck lower bound for 3XORSAT 
Mar 9  3XORSAT lower bound II 
Week 8  
Mar 14  Planted clique lower bound I: problem setting, basic algorithms, FeigeKrauthgamer degree 2 lower bound 
Mar 16  Planted clique lower bound II: FeigeKraughgamer moments, Kelner's polynomial, and the pseudocalibration relation 
Week 9  
Mar 21  Spring Break 
Mar 23  Spring Break 
Week 10  
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 
Week 11  
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 
Week 12  
Apr 11  Planted clique lower bound VII: wrapping up details of canonical factorization and last positivity proof ideas 
Apr 13  From pseudocalibration to lowdegree polynomial algorithms 
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 

Jan 4  Never  A few problems for you to check that you're prepared for this course (they won't be graded), as well as a survey about your background and interests. 
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