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

 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.