Standard

Exponential lower bound for static semi-algebraic proofs. / Grigoriev, Dima; Hirsch, Edward A.; Pasechnik, Dmitrii V.

Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings. 2002. стр. 257-268 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 2380 LNCS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование

Harvard

Grigoriev, D, Hirsch, EA & Pasechnik, DV 2002, Exponential lower bound for static semi-algebraic proofs. в Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 2380 LNCS, стр. 257-268, 29th International Colloquium on Automata, Languages, and Programming, ICALP 2002, Malaga, Испания, 8/07/02.

APA

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

Vancouver

Grigoriev D, Hirsch EA, Pasechnik DV. Exponential lower bound for static semi-algebraic proofs. в Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings. 2002. стр. 257-268. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

Author

Grigoriev, Dima ; Hirsch, Edward A. ; Pasechnik, Dmitrii V. / Exponential lower bound for static semi-algebraic proofs. Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings. 2002. стр. 257-268 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{e0093df03cf145cba40e7e27461c0363,
title = "Exponential lower bound for static semi-algebraic proofs",
abstract = "Semi-algebraic proof systems were introduced in [1] as extensions of Lov{\'a}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.",
author = "Dima Grigoriev and Hirsch, {Edward A.} and Pasechnik, {Dmitrii V.}",
year = "2002",
month = dec,
day = "1",
language = "English",
isbn = "3540438645",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "257--268",
booktitle = "Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings",
note = "29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 ; Conference date: 08-07-2002 Through 13-07-2002",

}

RIS

TY - GEN

T1 - Exponential lower bound for static semi-algebraic proofs

AU - Grigoriev, Dima

AU - Hirsch, Edward A.

AU - Pasechnik, Dmitrii V.

PY - 2002/12/1

Y1 - 2002/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=72949098117&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:72949098117

SN - 3540438645

SN - 9783540438649

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

SP - 257

EP - 268

BT - Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings

T2 - 29th International Colloquium on Automata, Languages, and Programming, ICALP 2002

Y2 - 8 July 2002 through 13 July 2002

ER -

ID: 49829085