Sums-of-squares integer programming relaxation: Lecture 7

by Massimo Lauria

Lecture 7: Sum of squares lower bound for k-SAT and k-XOR. Part 1/2.

Scribe: Ilario Bonacina


In this lecture we define the Positivstellensatz Calculus proof system and we show a lower bound for the degree needed to refute random k-XOR formulas. We define the Positivstellensatz Calculus, its subystem Binomial Calculus and prove a lower bound for the degree of random k-XOR formulas in Binomial Calculus. The proof of why this result leads to a lower bound for Positivstellensatz is in the next lecture.

Link: [Lecture notes 07]