The Sum-of-Squares (SOS) Proof System || @ CMU || Lecture 21(c) of CS Theory Toolkit

The Sum-of-Squares (SOS) Proof System || @ CMU || Lecture 21(c) of CS Theory Toolkit

by Ryan O'Donnell

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 Ryan O'Donnell 👥 14K 📅 June 22, 2020 ⏱ 22 min 👁 2K 📄 lecture 🧭 2026-08-17
Available in: English (current) Français

Keywords

Sum-of-SquaresSOSproof systemsemidefinite programmingcombinatorial optimization

Summary

This lecture, part of a graduate course on theoretical computer science, introduces the Sum-of-Squares (SOS) proof system, a powerful framework for certifying upper bounds on optimization problems. The instructor begins by motivating the SOS system as an SDP-based extension of the Sherali-Adams proof system, demonstrating that any non-negative polynomial on Boolean inputs can be represented as the multilinearization of a squared polynomial. This leads to a definition of SOS where axioms assert the non-negativity of squares of polynomials of bounded degree. The lecture highlights the equivalence of SOS with degree 2 to the basic SDP relaxation for Max Cut, and discusses the algorithmic efficiency of SOS, which can find proofs in polynomial time for constant degree. A key application is the ARV algorithm for approximating graph conductance, which uses SOS degree 4 to achieve a O(sqrt(log n)) approximation. The lecture also notes that SOS captures almost all known certification algorithms, making it a central tool in combinatorial optimization. However, it points out limitations, such as the failure of SOS to certify unsatisfiability for certain linear systems over finite fields. The lecture concludes with open problems, including the behavior of SOS on Unique Games and Max Bisection, and the difficulty of analyzing SOS beyond degree 2.

205 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides substantial value by presenting a coherent and rigorous introduction to the SOS proof system, connecting it to earlier topics like Sherali-Adams and semidefinite programming. The argumentation is solid: the instructor proves the key lemma that non-negative polynomials on Boolean inputs are multilinearizations of squares, and then builds the SOS system on this foundation. The discussion of applications, such as the ARV algorithm for conductance, illustrates the practical power of SOS. The lecture also critically examines limitations, noting that SOS fails on certain linear systems over finite fields, and discusses open problems, which adds depth. The presentation is well-structured, with clear definitions and examples, making it a valuable resource for advanced students and researchers.

Scientific Rigor, Source Quality, Title Accuracy

The lecture demonstrates scientific rigor through formal definitions, proofs, and references to known results. The instructor mentions the ARV algorithm and the work of Lasserre and Parrilo, but does not provide explicit citations within the lecture. The description includes a reference to a survey by Fleming, Kothari, and Pitassi, which is a relevant resource. The title accurately reflects the content, focusing on the SOS proof system. The lecture is part of a course, so it assumes prior knowledge, but the presentation is clear and technically sound.

217 words

Title / Content Match

The title accurately reflects the content, which focuses on the Sum-of-Squares proof system and its applications in combinatorial optimization.

Quality & Reliability

8/10

Content is a graduate-level lecture by a recognized expert in theoretical computer science, presenting formal definitions, proofs, and connections to known results. The presentation is rigorous and well-structured, though it lacks explicit citations to primary sources beyond the course context.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

  • Ryan O'Donnell's homepage — Instructor's academic page, providing background and related materials.
  • Course homepage on Diderot — Course page for CS Theory Toolkit, where lecture notes and resources are available.
  • Rebecca Kiger Photography — Photographer of the thumbnail, not directly related to content.

Concurring Sources

  • Semialgebraic Proofs and Efficient Algorithm Design — Survey mentioned in the description, likely covering SOS and related proof systems.

Contribution & Novelties

This lecture provides a clear and accessible introduction to the SOS proof system, emphasizing its role as a unifying framework for certification algorithms in combinatorial optimization. It connects SOS to earlier proof systems and SDP, and highlights its practical applications and limitations. The lecture is particularly valuable for its discussion of open problems and the difficulty of analyzing SOS beyond degree 2.

Pour aller plus loin :

105 words

Radar Profile

The radar profile shows high scores in quality of information and technical level, indicating a rigorous and advanced lecture. The quantity of information is also high, but the reliability score is slightly lower due to the lack of explicit citations. Overall, the lecture is well-balanced, with strengths in content depth and presentation.

Reliability 8/10