Sums-of-squares integer programming relaxation: Lecture 7
by Massimo Lauria
Lecture 7: Sum of squares lower bound for -SAT and -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 -XOR formulas. We define the Positivstellensatz Calculus, its subystem Binomial Calculus and prove a lower bound for the degree of random -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]