Lower bounds for cutting planes proofs with small coefficients

Maria Bonet, Toniann Pitassi, Ran Raz

Research output: Contribution to journalArticle

69 Scopus citations

Abstract

We consider small-weight Cutting Planes (CP*) proofs: that is, Cutting Planes (CP) proofs with coefficients up to Poly(n). We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP* proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution. We also prove the following two theorems: (1) Tree-like CP* proofs cannot polynomially simulate non-tree-like CP* proofs. (2) Tree-like CP* proofs and Bounded-depth-Frege proofs cannot polynomially simulate each other. Our proofs also work for some generalizations of the CP* proof system. In particular, they work for CP* with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference.

Original languageEnglish (US)
Pages (from-to)708-728
Number of pages21
JournalJournal of Symbolic Logic
Volume62
Issue number3
DOIs
StatePublished - Sep 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Philosophy
  • Logic

Fingerprint Dive into the research topics of 'Lower bounds for cutting planes proofs with small coefficients'. Together they form a unique fingerprint.

  • Cite this