### Sums-of-squares integer programming relaxation: Lecture 8

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

Scribe: Mohamed Abdalmoaty

## Abstract

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.