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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International