Videos

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

Presenter
December 18, 2012
Keywords:
  • Computer Science and Discrete Mathematics (CSDM)
Abstract
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.