Sum of squares bounds for the total ordering principle

12/04/2018
by   Aaron Potechin, et al.
0

In this paper, we analyze the sum of squares hierarchy (SOS) on the total ordering principle on n elements. We show that degree Õ(√(n)) SOS can prove the total ordering principle so in this setting SOS is considerably more powerful than resolution, polynomial calculus, and the Sherali-Adams hierarchy. We also show superconstant degree SOS lower bounds which we believe can be improved to degree Ω̃(√(n)).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset