# Open Collections

## BIRS Workshop Lecture Videos

### Sum of Squares Bounds for the Ordering Principle Potechin, Aaron

#### Description

The ordering principle, which says that if there is an ordering on n elements then one of them must be less than all of the others, is an important example in proof complexity. The ordering principle is important because while it has a short resolution proof, any resolution proof must have width \$\Omega(n)\$ and any polynomial calculus proof must have degree \$\Omega(n)\$. Thus, with some adjustments, the ordering principle gives a tight example for the size/width tradeoffs of Ben-Sasson and Wigderson for resolution and the size/degree tradeoffs of Impagliazzo, Pudlak, and Sgall for polynomial calculus (as it requires \$n^2\$ variables to express the ordering principle). A natural question is whether the sum of squares hierarchy also requires degree \$\Omega(n)\$ to prove the ordering principle or if sum of squares can do better. As it turns out, sum of squares can do better. In this talk, I will describe how the sum of squares hierarchy can prove the ordering principle using degree roughly \$n^(1/2)\$. Time permitting, I will also describe ideas for a sum of squares lower bound.