BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Sum of Squares Bounds for the Ordering Principle Potechin, Aaron


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International