Sums-of-squares integer programming relaxation: Lecture 8

by Massimo Lauria

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

Scribe: Mohamed Abdalmoaty


This whole lecture is devote to show that if a k-XOR formula \phi requires degree D refutations in Binomial Calculus (BC), then it requires degree D/2 Positivstellensatz Calculus refutations (\mathsf{PC}_>).

In the last lecture we already showed that for a random k-XOR formula the required degree D is large, therefore this part will conclude the proof of the lower bound for the degree of \mathsf{PC}_> refutations of random $k$-XORs.

Link: [Lecture notes 08]