Sums-of-squares integer programming relaxation: Lecture 8
by Massimo Lauria
Lecture 8: Sum of squares lower bound for -SAT and -XOR. Part 2/2.
Scribe: Mohamed Abdalmoaty
This whole lecture is devote to show that if a -XOR formula requires degree refutations in Binomial Calculus (BC), then it requires degree Positivstellensatz Calculus refutations ().
In the last lecture we already showed that for a random -XOR formula the required degree is large, therefore this part will conclude the proof of the lower bound for the degree of refutations of random $k$-XORs.
Link: [Lecture notes 08]