### 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 language | English |
---|---|

Title of host publication | Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings |

Pages | 257-268 |

Number of pages | 12 |

Publication status | Published - 1 Dec 2002 |

Event | 29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 - Malaga Duration: 8 Jul 2002 → 13 Jul 2002 |

### Publication series

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

Volume | 2380 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

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

Country | Spain |

City | Malaga |

Period | 8/07/02 → 13/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).