Complexity of semi-algebraic proofs

• Main Authors: Grigoriev, Dima, Hirsch, Edward A., Pasechnik, Dmitrii V.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2013
• Online Access: https://hdl.handle.net/10356/95181; http://hdl.handle.net/10220/9273
• Institution: Nanyang Technological University

Proof systems for polynomial inequalities in 0-1 variables include the well-studied Cutting Planes proof system (CP) and the Lovász- Schrijver calculi (LS) utilizing linear, respectively, quadratic, inequalities. We introduce generalizations LSd of LS involving polynomial inequalities of degree at m...