Complexity of semi-algebraic proofs

Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik

Research outputpeer-review

24 Citations (Scopus)

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 LSd of LSinvolving polynomial inequalities of degree at most d.Surprisingly, the systems LSd turn out to be very strong. We construct polynomial-size bounded degree LSd 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 languageEnglish
Title of host publicationSTACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsAfonso Ferreira, Helmut Alt
PublisherSpringer Nature
Pages419-430
Number of pages12
ISBN (Electronic)9783540432838
Publication statusPublished - 1 Jan 2002
Event19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002 - Antibes - Juan les Pins
Duration: 14 Mar 200216 Mar 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2285
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002
CountryFrance
CityAntibes - Juan les Pins
Period14/03/0216/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

    Grigoriev, D., Hirsch, E. A., & Pasechnik, D. V. (2002). Complexity of semi-algebraic proofs. In A. Ferreira, & H. Alt (Eds.), 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.