Exponential lower bound for static semi-algebraic proofs

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

Research output

4 Citations (Scopus)

Abstract

Semi-algebraic proof systems were introduced in [1] as extensions of Lovász-Schrijver proof systems [2,3].These systems are very strong; in particular, they have short proofs of Tseitin's tautologies, the pigeonhole principle, the symmetric knapsack problem and the cliquecoloring tautologies [1]. In this paper we study static versions of these systems.W e prove an exponential lower bound on the length of proofs in one such system.The same bound for two tree-like (dynamic) systems follows.The proof is based on a lower bound on the "Boolean degree" of Positivstellensatz Calculus refutations of the symmetric knapsack problem.

Original languageEnglish
Title of host publicationAutomata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings
Pages257-268
Number of pages12
Publication statusPublished - 1 Dec 2002
Event29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 - Malaga
Duration: 8 Jul 200213 Jul 2002

Publication series

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

Conference

Conference29th International Colloquium on Automata, Languages, and Programming, ICALP 2002
CountrySpain
CityMalaga
Period8/07/0213/07/02

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Exponential lower bound for static semi-algebraic proofs'. Together they form a unique fingerprint.

  • Cite this

    Grigoriev, D., Hirsch, E. A., & Pasechnik, D. V. (2002). Exponential lower bound for static semi-algebraic proofs. In Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings (pp. 257-268). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2380 LNCS).