The SOS (aka Lassere/Positivestellensatz/Sum-of-Squares) System Series

The SOS (aka Sum-of-Squares) System Series Raghu Meka (1) and Avi Wigderson (2)

Raghu Meka (1) and Avi Wigderson (2)
DIMACS (1) and Professor, School of Mathematics, IAS (2)
December 18, 2012

We will give an overview of this system, which has been at the center of recent algorithmic and proof complexity developments. We will give the definitions of the system (as a proof system for polynomial inequalities, and as an SDP-based algorithm), and basic upper and lower bounds for it. In particular we'll explain the recent SOS-proof of the hypercontractive inequality for the noisy hypercube of Barak et al., as well as the degree lower bounds for proving Tseitin and Knapsack tautologies of Grigoriev.