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

#### by Massimo Lauria

**Lecture 7:** Sum of squares lower bound for -SAT and -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 -XOR formulas. We define the Positivstellensatz Calculus, its subystem Binomial Calculus and prove a lower bound for the degree of random -XOR formulas in Binomial Calculus. The proof of why this result leads to a lower bound for Positivstellensatz is in the next lecture.

Link: [Lecture notes 07]

Advertisements