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

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

Scribe: Ilario Bonacina

## Abstract

In this lecture we define the Positivstellensatz Calculus proof system and we show a lower bound for the degree needed to refute random $k$-XOR formulas. We define the Positivstellensatz Calculus, its subystem Binomial Calculus and prove a lower bound for the degree of random $k$-XOR formulas in Binomial Calculus. The proof of why this result leads to a lower bound for Positivstellensatz is in the next lecture.