### Abstract

Proof systems for polynomial inequalities in 0-1 variables include the well-studied Cutting Planes proof system (CP) and the Lov´asz-Schrijver calculi (LS) utilizing linear, respectively, quadratic, inequalities. We introduce generalizations LS^{d} of LSinvolving polynomial inequalities of degree at most d.Surprisingly, the systems LS^{d} turn out to be very strong. We construct polynomial-size bounded degree LS^{d} proofs of the clique-coloring tautologies (which have no polynomial-size CP proofs), the symmetric knapsack problem (which has no bounded degree Positivstellensatz Calculus (PC) proofs), and Tseitin’s tautologies (hard for many known proof systems). Extending our systems with a division rule yields a polynomial simulation of CP with polynomially bounded coefficients, while other extra rules further reduce the proof degrees for the aforementioned examples. Finally, we prove lower bounds on Lov´asz-Schrijver ranks, demonstrating, in particular, their rather limited applicability for proof complexity.

Original language | English |
---|---|

Title of host publication | STACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings |

Editors | Afonso Ferreira, Helmut Alt |

Publisher | Springer Nature |

Pages | 419-430 |

Number of pages | 12 |

ISBN (Electronic) | 9783540432838 |

Publication status | Published - 1 Jan 2002 |

Event | 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002 - Antibes - Juan les Pins Duration: 14 Mar 2002 → 16 Mar 2002 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2285 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002 |
---|---|

Country | France |

City | Antibes - Juan les Pins |

Period | 14/03/02 → 16/03/02 |

### Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Complexity of semi-algebraic proofs'. Together they form a unique fingerprint.

## Cite this

*STACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings*(pp. 419-430). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2285). Springer Nature.