{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T21:30:44Z","timestamp":1782941444996,"version":"3.54.5"},"reference-count":46,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":6128,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1997,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A proof of the (propositional) Craig interpolation theorem for cut-free sequent calculus yields that a sequent with a cut-free proof (or with a proof with cut-formulas of restricted form; in particular, with only analytic cuts) with<jats:italic>k<\/jats:italic>inferences has an interpolant whose circuit-size is at most<jats:italic>k<\/jats:italic>. We give a new proof of the interpolation theorem based on a communication complexity approach which allows a similar estimate for a larger class of proofs. We derive from it several corollaries:<jats:list><jats:list-item><jats:label>(1)<\/jats:label><jats:p>Feasible interpolation theorems for the following proof systems:<\/jats:p><jats:list><jats:list-item><jats:label>(a)<\/jats:label><jats:p>resolution<\/jats:p><\/jats:list-item><jats:list-item><jats:label>(b)<\/jats:label><jats:p>a subsystem of<jats:italic>LK<\/jats:italic>corresponding to the bounded arithmetic theory<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200016303_inline1\"\/>(<jats:italic>\u03b1<\/jats:italic>)<\/jats:p><\/jats:list-item><jats:list-item><jats:label>(c)<\/jats:label><jats:p>linear equational calculus<\/jats:p><\/jats:list-item><jats:list-item><jats:label>(d)<\/jats:label><jats:p>cutting planes.<\/jats:p><\/jats:list-item><\/jats:list><\/jats:list-item><jats:list-item><jats:label>(2)<\/jats:label><jats:p>New proofs of the exponential lower bounds (for new formulas)<\/jats:p><jats:list><jats:list-item><jats:label>(a)<\/jats:label><jats:p>for resolution ([15])<\/jats:p><\/jats:list-item><jats:list-item><jats:label>(b)<\/jats:label><jats:p>for the cutting planes proof system with coefficients written in unary ([4]).<\/jats:p><\/jats:list-item><\/jats:list><\/jats:list-item><jats:list-item><jats:label>(3)<\/jats:label><jats:p>An alternative proof of the independence result of [43] concerning the provability of circuit-size lower bounds in the bounded arithmetic theory<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200016303_inline1\"\/>(<jats:italic>\u03b1<\/jats:italic>).<\/jats:p><\/jats:list-item><\/jats:list><\/jats:p><jats:p>In the other direction we show that a depth 2 subsystem of<jats:italic>LK<\/jats:italic>does not admit feasible monotone interpolation theorem (the so called Lyndon theorem), and that a feasible monotone interpolation theorem for the depth 1 subsystem of<jats:italic>LK<\/jats:italic>would yield new exponential lower bounds for resolution proofs of the weak pigeonhole principle.<\/jats:p>","DOI":"10.2307\/2275541","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T23:01:20Z","timestamp":1146956480000},"page":"457-486","source":"Crossref","is-referenced-by-count":177,"title":["Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic"],"prefix":"10.1017","volume":"62","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200016303_ref008","first-page":"83","volume-title":"Proceedings of the 7th Annual ACM Symposium on Theory of Computing","author":"Cook","year":"1975"},{"key":"S0022481200016303_ref005","volume-title":"Bounded arithmetic","author":"Buss","year":"1986"},{"key":"S0022481200016303_ref004","doi-asserted-by":"crossref","unstructured":"Bonet M. L. , Pitassi T. , and Raz R. , Lower bounds for cutting planes proofs with small coefficients, preprint, 1994.","DOI":"10.1145\/225058.225275"},{"key":"S0022481200016303_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 ANSSSR"},{"key":"S0022481200016303_ref011","first-page":"250","volume":"22","author":"Craig","year":"1957","journal-title":"Linear reasoning: A new form of the Herbrand-Gentzen theorem"},{"key":"S0022481200016303_ref009","first-page":"36","volume":"44","author":"Cook","year":"1979","journal-title":"The relative efficiency of prepositional proof systems"},{"key":"S0022481200016303_ref040","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1093\/oso\/9780198536901.003.0012","volume-title":"Arithmetic, Proof Theory and Computational Complexity","author":"Razborov","year":"1993"},{"key":"S0022481200016303_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(76)90167-5"},{"key":"S0022481200016303_ref024","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19900360106"},{"key":"S0022481200016303_ref003","volume-title":"The foundations of mathematics","author":"Beth","year":"1959"},{"key":"S0022481200016303_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"S0022481200016303_ref034","first-page":"494","volume":"36","author":"Parikh","year":"1971","journal-title":"Existence and feasibility in arithmetic"},{"key":"S0022481200016303_ref007","unstructured":"Chiari M. and Kraj\u00ed\u010dek J. , Witnessing functions in bounded arithmetic and search problems, submitted, 1994."},{"key":"S0022481200016303_ref042","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"S0022481200016303_ref027","doi-asserted-by":"publisher","DOI":"10.1007\/BF01531024"},{"key":"S0022481200016303_ref041","doi-asserted-by":"crossref","unstructured":"Razborov A. A. , On provably disjoint NP-pairs, preprint, 1994.","DOI":"10.7146\/brics.v1i36.21607"},{"key":"S0022481200016303_ref037","first-page":"1235","volume":"53","author":"Paris","year":"1988","journal-title":"Provability of the pigeonhole principle and the existence of infinitely many primes"},{"key":"S0022481200016303_ref012","first-page":"269","volume":"22","author":"Craig","year":"1957","journal-title":"Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory"},{"key":"S0022481200016303_ref035","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0075316"},{"key":"S0022481200016303_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90039-4"},{"key":"S0022481200016303_ref016","first-page":"539","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing","author":"Karchmer","year":"1988"},{"key":"S0022481200016303_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(90)90023-U"},{"key":"S0022481200016303_ref032","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(84)90029-0"},{"key":"S0022481200016303_ref018","first-page":"287","volume-title":"Logic from Computer Science, Proceedings of a workshop held November 13\u201317, 1989, in Berkeley, Mathematical Sciences Research Institute Publication","author":"Kraj\u00ed\u010dek","year":"1992"},{"key":"S0022481200016303_ref019","first-page":"73","volume":"59","author":"Kraj\u00ed\u010dek","year":"1994","journal-title":"Lower bounds to the size of constant-depth prepositional proofs"},{"key":"S0022481200016303_ref021","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_10"},{"key":"S0022481200016303_ref022","first-page":"1063","volume":"54","author":"Kraj\u00ed\u010dek","year":"1989","journal-title":"Prepositional proof systems, the consistency of first order theories and the complexity of computations"},{"key":"S0022481200016303_ref023","first-page":"193","volume-title":"Computer Science Logic","author":"Kraj\u00ed\u010dek","year":"1989"},{"key":"S0022481200016303_ref025","volume-title":"Proceedings of the meeting Logic and Computational Complexity","author":"Kraj\u00ed\u010dek","year":"1995"},{"key":"S0022481200016303_ref028","volume-title":"Technical report nb. 3","author":"Kreisel","year":"1961"},{"key":"S0022481200016303_ref029","volume-title":"Pseudo-randomness and applications","author":"Luby","year":"1993"},{"key":"S0022481200016303_ref033","volume-title":"Computational complexity","author":"Papadimitriou","year":"1994"},{"key":"S0022481200016303_ref031","first-page":"345","volume-title":"Proceedings of Logic Colloquium 1982","author":"Mundici","year":"1984"},{"key":"S0022481200016303_ref036","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0168-0072(87)90066-2","article-title":"On the scheme of induction for bounded arithmetic formulas","volume":"35","author":"Paris","year":"1987","journal-title":"Annals of Pure and Applied Logic"},{"key":"S0022481200016303_ref038","doi-asserted-by":"publisher","DOI":"10.1137\/0204018"},{"key":"S0022481200016303_ref039","first-page":"354","article-title":"Lower bounds on the monotone complexity of some Boolean functions","volume":"31","author":"Razborov","year":"1985","journal-title":"Soviet Mathem. Doklady"},{"key":"S0022481200016303_ref043","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":"S0022481200016303_ref044","first-page":"204","volume-title":"Proceedings of the 26th Annual ACM Symposium on Theory of Computing","author":"Razborov","year":"1994"},{"key":"S0022481200016303_ref045","volume-title":"Proof theory","author":"Takeuti","year":"1975"},{"key":"S0022481200016303_ref046","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1093\/oso\/9780198536901.003.0016","volume-title":"Arithmetic, Proof Theory and Computational Complexity","author":"Takeuti","year":"1993"},{"key":"S0022481200016303_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90072-2"},{"key":"S0022481200016303_ref014","first-page":"175","volume-title":"Proceedings of Logic Colloquium 1983","author":"Gurevich","year":"1984"},{"key":"S0022481200016303_ref026","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-3466-1_15"},{"key":"S0022481200016303_ref030","doi-asserted-by":"publisher","DOI":"10.1007\/BF02023010"},{"key":"S0022481200016303_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"S0022481200016303_ref020","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200016303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,4]],"date-time":"2024-02-04T07:29:00Z","timestamp":1707031740000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200016303\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,6]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,6]]}},"alternative-id":["S0022481200016303"],"URL":"https:\/\/doi.org\/10.2307\/2275541","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,6]]}}}