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

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

**Scribe:** Mohamed Abdalmoaty

## Abstract

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]