{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T14:08:57Z","timestamp":1781014137673,"version":"3.54.1"},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":6036,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1997,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider small-weight Cutting Planes (CP*) proofs; that is, Cutting Planes (CP) proofs with coefficients up to Poly(<jats:italic>n<\/jats:italic>). 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.<\/jats:p><jats:p>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.<\/jats:p><jats:p>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.<\/jats:p>","DOI":"10.2307\/2275569","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T23:01:58Z","timestamp":1146956518000},"page":"708-728","source":"Crossref","is-referenced-by-count":75,"title":["Lower bounds for cutting planes proofs with small coefficients"],"prefix":"10.1017","volume":"62","author":[{"given":"Maria","family":"Bonet","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200015991_ref011","article-title":"Cuttingplane versus Frege proof systems","volume":"533","author":"Goerdt","journal-title":"Lecture Notes in Computer Science"},{"key":"S0022481200015991_ref030","first-page":"209","volume-title":"11th Symposium on Theoretical Computer Science","author":"Yao","year":"1979"},{"key":"S0022481200015991_ref028","first-page":"201","article-title":"Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic","volume":"59","author":"Razborov","year":"1995","journal-title":"Izvestiya of the R.A.N."},{"key":"S0022481200015991_ref025","first-page":"562","volume-title":"Proceedings of the 30th FOCS","author":"Raz","year":"1989"},{"key":"S0022481200015991_ref023","unstructured":"Pudl\u00e1k P. , manuscript in preparation."},{"key":"S0022481200015991_ref022","first-page":"1235","volume":"53","author":"Paris","year":"1988","journal-title":"Provability of the pigeonhole principle and the existence of infinitely many primes"},{"key":"S0022481200015991_ref021","unstructured":"Clote P. , Cutting planes and constant depth Frege proofs, manuscript, 1993."},{"key":"S0022481200015991_ref029","first-page":"204","volume-title":"Proceedings from the Twenty-sixth ACM Symposium on Theoretical Computer Science","author":"Razborov","year":"1994"},{"key":"S0022481200015991_ref020","unstructured":"Kushilevitz E. and Nisan N. , Communication complexity, to appear."},{"key":"S0022481200015991_ref018","first-page":"73","volume":"59","author":"Kraj\u00ed\u010dek","year":"1994","journal-title":"Lower bounds to the size of constant-depth propositional proofs"},{"key":"S0022481200015991_ref014","volume-title":"Proceedings from Logic in Computer Science","author":"Impagliazzo","year":"1994"},{"key":"S0022481200015991_ref027","first-page":"798","article-title":"Lower bounds for the monotone complexity of some Boolean functions","volume":"281","author":"Razborov","year":"1985","journal-title":"Dokl. Ak. Nauk. SSSR"},{"key":"S0022481200015991_ref004","first-page":"188","volume-title":"Symposium on Theoretical Computer Science","author":"Beame","year":"1992"},{"key":"S0022481200015991_ref001","first-page":"346","volume-title":"29th Annual Symposium on the Foundations of Computer Science","author":"Ajtai","year":"1988"},{"key":"S0022481200015991_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"S0022481200015991_ref015","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1948.001.0001","volume-title":"Communication complexity: A new approach to circuit depth","author":"Karchmer","year":"1989"},{"key":"S0022481200015991_ref003","first-page":"200","volume-title":"Symposium on Theoretical Computer Science","author":"Beame","year":"1992"},{"key":"S0022481200015991_ref016","first-page":"539","volume-title":"Proceedings of the 20th STOC","author":"Karchmer","year":"1988"},{"key":"S0022481200015991_ref009","first-page":"36","volume":"44","author":"Cook","year":"1979","journal-title":"The relative efficiency of propositional proof systems"},{"key":"S0022481200015991_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90167-2"},{"key":"S0022481200015991_ref024","unstructured":"Raz R. , Lower bounds for probabilistic communication complexity and for the depth of monotone Boolean circuits, Ph.D. thesis , The Hebrew University, 1992, in Hebrew."},{"key":"S0022481200015991_ref017","unstructured":"Kraj\u00ed\u010dek J. , Interpolation theorems, lower bounds for proof systems and independence results for bounded arithmetic, to appear in this Journal."},{"key":"S0022481200015991_ref012","first-page":"269","volume-title":"Recent advances in mathematical programming","author":"Gomory","year":"1963"},{"key":"S0022481200015991_ref006","volume-title":"Archive for Mathematical Logic","author":"Buss"},{"key":"S0022481200015991_ref005","first-page":"916","volume":"52","author":"Buss","year":"1987","journal-title":"Polynomial size proofs of the propositional pigeonhole principle"},{"key":"S0022481200015991_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90039-4"},{"key":"S0022481200015991_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"S0022481200015991_ref019","doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek J. and Pudl\u00e1k P. , Some consequences of cryptographical conjectures for EF, manuscript, 1995.","DOI":"10.1007\/3-540-60178-3_86"},{"key":"S0022481200015991_ref008","unstructured":"Cook S. and Haken A. , manuscript in preparation."},{"key":"S0022481200015991_ref026","first-page":"287","volume-title":"ACM Symposium on Theory of Computing","author":"Raz","year":"1990"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200015991","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T14:23:42Z","timestamp":1586874222000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200015991\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,9]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,9]]}},"alternative-id":["S0022481200015991"],"URL":"https:\/\/doi.org\/10.2307\/2275569","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,9]]}}}