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.