|Computer Science/Discrete Mathematics Seminar II|
|Topic:||The SOS (aka Lassere/Positivestellensatz/Sum-of-Squares) System|
|Speaker:||(1) Raghu Meka and (2) Avi Wigderson|
|Affiliation:||(1) DIMACS; (2) IAS|
|Date:||Tuesday, December 18|
|Time/Room:||10:30am - 12:30pm/S-101|
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.