Sum of squares bounds for the ordering principle

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 $ε> 0$, SOS requires degree $Ω(n^{\frac{1}{2} - ε})$ to prove the ordering principle on $n$ elements.

No reviews yet.

No comments yet.