ECCC-Report TR17-154https://eccc.weizmann.ac.il/report/2017/154Comments and Revisions published for TR17-154en-usThu, 12 Oct 2017 14:55:10 +0300
Paper TR17-154
| The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs |
Christoph Berkholz
https://eccc.weizmann.ac.il/report/2017/154We relate different approaches for proving the unsatisfiability of a system of real polynomial equations over Boolean variables. On the one hand, there are the static proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, we consider polynomial calculus, which is a dynamic algebraic proof system that models GrÃ¶bner basis computations.
Our first result is that sum-of-squares simulates polynomial calculus: any polynomial calculus refutation of degree $d$ can be transformed into a sum-of-squares refutation of degree $2d$ and only polynomial increase in size. In contrast, our second result shows that this is not the case for Sherali-Adams: there are systems of polynomial equations that have polynomial calculus refutations of degree $3$ and polynomial size, but require Sherali-Adams refutations of degree $\Omega(\sqrt{n}/\log n)$ and exponential size.Thu, 12 Oct 2017 14:55:10 +0300https://eccc.weizmann.ac.il/report/2017/154