Sum of squares bounds for the ordering principle

Abstract

In this paper, we analyze the sum of squares hierarchy (SOS) on the ordering principle on $n$ elements. We prove that degree $O(\sqrt{n}log(n))$ SOS can prove the ordering principle. We then show that this upper bound is essentially tight by proving that for any $\epsilon >0$, SOS requires degree $\Omega (n^{\frac{1}{2}-\epsilon })$ to prove the ordering principle on $n$ elements.

References in corpus (1)

• Hypercontractivity, Sum-of-Squares Proofs, and their Applications