{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T12:01:28Z","timestamp":1759147288298},"reference-count":26,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":5580,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1998,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We define a first-order extension LK(CP) of the cutting planes proof system CP as the first-order sequent calculus LK whose atomic formulas are CP-inequalities <jats:italic>\u2211<jats:sub>i<\/jats:sub> a<jats:sub>i<\/jats:sub><\/jats:italic> \u00b7 <jats:italic>x<jats:sub>i<\/jats:sub><\/jats:italic> \u2265 <jats:italic>b<\/jats:italic> (<jats:italic>x<jats:sub>i<\/jats:sub><\/jats:italic>'s variables, <jats:italic>a<jats:sub>i<\/jats:sub><\/jats:italic>'s and <jats:italic>b<\/jats:italic> constants). We prove an interpolation theorem for LK(CP) yielding as a corollary a conditional lower bound for LK(CP)-proofs. For a subsystem R(CP) of LK(CP), essentially resolution working with clauses formed by CP-inequalities, we prove a monotone interpolation theorem obtaining thus an unconditional lower bound (depending on the maximum size of coefficients in proofs and on the maximum number of CP-inequalities in clauses). We also give an interpolation theorem for polynomial calculus working with sparse polynomials.<\/jats:p><jats:p>The proof relies on a universal interpolation theorem for semantic derivations [16, Theorem 5.1].<\/jats:p><jats:p>LK(CP) can be viewed as a two-sorted first-order theory of Z considered itself as a discretely ordered Z-module. One sort of variables are module elements, another sort are scalars. The quantification is allowed only over the former sort. We shall give a construction of a theory LK(M) for any discretely ordered module M (e.g., LK(Z) extends LK(CP)). The interpolation theorem generalizes to these theories obtained from discretely ordered Z-modules. We shall also discuss a connection to quantifier elimination for such theories.<\/jats:p><jats:p>We formulate a communication complexity problem whose (suitable) solution would allow to improve the monotone interpolation theorem and the lower bound for R(CP).<\/jats:p>","DOI":"10.2307\/2586668","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T14:01:33Z","timestamp":1146924093000},"page":"1582-1596","source":"Crossref","is-referenced-by-count":18,"title":["Discretely ordered modules as a first-order extension of the cutting planes proof system"],"prefix":"10.1017","volume":"63","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200014432_ref026","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(92)90025-U"},{"key":"S0022481200014432_ref025","volume-title":"Proof theory","author":"Takeuti","year":"1975"},{"key":"S0022481200014432_ref024","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00007-0"},{"key":"S0022481200014432_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90039-4"},{"key":"S0022481200014432_ref012","first-page":"539","volume-title":"Proceedings of the 20th annual ACM Symposium on theory of computing","author":"Karchmer","year":"1988"},{"key":"S0022481200014432_ref002","first-page":"1033","article-title":"On a method for obtaining lower bounds for the complexity of individual monotone functions","volume":"282","author":"Andreev","year":"1985","journal-title":"Doklady AN SSSR"},{"key":"S0022481200014432_ref023","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":"S0022481200014432_ref018","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"S0022481200014432_ref007","first-page":"36","volume":"44","author":"Cook","year":"1979","journal-title":"The relative efficiency of propositional proof systems"},{"key":"S0022481200014432_ref021","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/039\/15"},{"key":"S0022481200014432_ref019","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970203"},{"key":"S0022481200014432_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60178-3_86"},{"key":"S0022481200014432_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"S0022481200014432_ref003","first-page":"603","volume-title":"Proceedings of the 28th annual ACM Symposium on theory of computing","author":"Babai","year":"1996"},{"key":"S0022481200014432_ref004","first-page":"575","volume-title":"Proceedings of the 27th annual ACM Symposium on theory of computing","author":"Bonet","year":"1995"},{"key":"S0022481200014432_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294258"},{"key":"S0022481200014432_ref006","first-page":"174","volume-title":"Proceedings of the 28th annual ACM Symp. on theory of computing","author":"Clegg","year":"1996"},{"key":"S0022481200014432_ref009","first-page":"27","article-title":"Superexponential complexity of Presburger's arithmetic","volume":"7","author":"Fisher","year":"1974","journal-title":"SIAM-AMS Proceedings"},{"key":"S0022481200014432_ref010","article-title":"An exponential lower bound for the size of monotone real circuits","author":"Haken","year":"1995","journal-title":"Journal of Computer and System Science"},{"key":"S0022481200014432_ref011","unstructured":"Impagliazzo R. and Pitassi T. , Interpolation for generalized cutting planes proof systems, a report in the CZ\u2013US email seminar written by Pitassi T. , 1996."},{"key":"S0022481200014432_ref013","first-page":"73","volume":"59","author":"Kraj\u00ed\u010dek","year":"1994","journal-title":"Lower bounds to the size of constant-depth propositionai proofs"},{"key":"S0022481200014432_ref014","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"key":"S0022481200014432_ref015","volume-title":"Mathematical Logic Quarterly","author":"Kraj\u00ed\u010dek","year":"1996"},{"key":"S0022481200014432_ref016","first-page":"457","volume":"62","author":"Kraj\u00ed\u010dek","year":"1997","journal-title":"Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic"},{"key":"S0022481200014432_ref020","first-page":"605","volume":"62","author":"Pudl\u00e1k","year":"1997","journal-title":"Lower bounds for resolution and cutting planes proofs and monotone computations"},{"key":"S0022481200014432_ref022","first-page":"354","article-title":"Lower bounds on the monotone complexity of some Boolean functions","volume":"31","author":"Razborov","year":"1985","journal-title":"Soviet Mathematics. Doklady"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200014432","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T15:53:13Z","timestamp":1557503593000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200014432\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,12]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,12]]}},"alternative-id":["S0022481200014432"],"URL":"https:\/\/doi.org\/10.2307\/2586668","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,12]]}}}