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.