Open Collections

Sum of Squares Bounds for the Ordering Principle

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Computer science; Mathematical logic and foundations; Theoretical computer science

video/mp4

Author affiliation: University of Chicago

2020-07-20

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/75213

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/