{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T04:09:45Z","timestamp":1754107785168},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Math. Log."],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:p> The feasible interpolation theorem for semantic derivations from [J. Kraj\u00ed\u010dek, Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, J. Symbolic Logic 62(2) (1997) 457\u2013486] allows to derive from some short semantic derivations (e.g. in resolution) of the disjointness of two [Formula: see text] sets [Formula: see text] and [Formula: see text] a small communication protocol (a general dag-like protocol in the sense of Kraj\u00ed\u010dek (1997) computing the Karchmer\u2013Wigderson multi-function [Formula: see text] associated with the sets, and such a protocol further yields a small circuit separating [Formula: see text] from [Formula: see text]. When [Formula: see text] is closed upwards, the protocol computes the monotone Karchmer\u2013Wigderson multi-function [Formula: see text] and the resulting circuit is monotone. Kraj\u00ed\u010dek [Interpolation by a game, Math. Logic Quart. 44(4) (1998) 450\u2013458] extended the feasible interpolation theorem to a larger class of semantic derivations using the notion of a real communication complexity (e.g. to the cutting planes proof system CP). In this paper, we generalize the method to a still larger class of semantic derivations by allowing randomized protocols. We also introduce an extension of the monotone circuit model, monotone circuits with a local oracle (CLOs), that does correspond to communication protocols for [Formula: see text] making errors. The new randomized feasible interpolation thus shows that a short semantic derivation (from a certain class of derivations larger than in the original method) of the disjointness of [Formula: see text], [Formula: see text] closed upwards, yields a small randomized protocol for [Formula: see text] and hence a small monotone CLO separating the two sets. This research is motivated by the open problem to establish a lower bound for proof system [Formula: see text] operating with clauses formed by linear Boolean functions over [Formula: see text]. The new randomized feasible interpolation applies to this proof system and also to (the semantic versions of) cutting planes CP, to small width resolution over CP of Kraj\u00ed\u010dek [Discretely ordered modules as a first-order extension of the cutting planes proof system, J. Symbolic Logic 63(4) (1998) 1582\u20131596] (system R(CP)) and to random resolution RR of Buss, Kolodziejczyk and Thapen [Fragments of approximate counting, J. Symbolic Logic 79(2) (2014) 496\u2013525]. The method does not yield yet lengths-of-proofs lower bounds; for this it is necessary to establish lower bounds for randomized protocols or for monotone CLOs. <\/jats:p>","DOI":"10.1142\/s0219061318500125","type":"journal-article","created":{"date-parts":[[2018,7,6]],"date-time":"2018-07-06T03:14:40Z","timestamp":1530846880000},"page":"1850012","source":"Crossref","is-referenced-by-count":6,"title":["Randomized feasible interpolation and monotone circuits with a local oracle"],"prefix":"10.1142","volume":"18","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[{"name":"Department of Algebra, Faculty of Mathematics and Physics, Charles University, Sokolovsk\u00e1 83, Prague 8, CZ 186 75, The Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2018,11,20]]},"reference":[{"key":"S0219061318500125BIB001","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389944"},{"key":"S0219061318500125BIB002","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"S0219061318500125BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"S0219061318500125BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294258"},{"key":"S0219061318500125BIB005","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2013.37"},{"key":"S0219061318500125BIB006","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2015-06233-3"},{"key":"S0219061318500125BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.12.006"},{"key":"S0219061318500125BIB014","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"key":"S0219061318500125BIB016","doi-asserted-by":"publisher","DOI":"10.2307\/2275541"},{"key":"S0219061318500125BIB017","doi-asserted-by":"publisher","DOI":"10.2307\/2586668"},{"key":"S0219061318500125BIB018","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19980440403"},{"key":"S0219061318500125BIB019","doi-asserted-by":"publisher","DOI":"10.4064\/fm170-1-8"},{"key":"S0219061318500125BIB021","first-page":"1","volume":"2018","author":"Kraj\u00ed\u010dek J.","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"S0219061318500125BIB022","first-page":"301","volume":"1","author":"Nisan N.","year":"1993","journal-title":"Combinatorics"},{"key":"S0219061318500125BIB023","doi-asserted-by":"publisher","DOI":"10.2307\/2275583"},{"key":"S0219061318500125BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(98)80023-2"},{"key":"S0219061318500125BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2008.04.001"},{"key":"S0219061318500125BIB028","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"S0219061318500125BIB029","first-page":"354","volume":"31","author":"Razborov A. A.","year":"1985","journal-title":"Sov. Math. Dokl."},{"issue":"4","key":"S0219061318500125BIB030","first-page":"598","volume":"41","author":"Razborov A. A.","year":"1987","journal-title":"Mat. Zametki"},{"issue":"1","key":"S0219061318500125BIB031","first-page":"201","volume":"59","author":"Razborov A. A.","year":"1995","journal-title":"Izv. Ross. Akad. Nauk Ser. Mat."},{"key":"S0219061318500125BIB032","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050013"}],"container-title":["Journal of Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219061318500125","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:55:47Z","timestamp":1565114147000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219061318500125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,20]]},"references-count":22,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2018,11,20]]},"published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1142\/S0219061318500125"],"URL":"https:\/\/doi.org\/10.1142\/s0219061318500125","relation":{},"ISSN":["0219-0613","1793-6691"],"issn-type":[{"value":"0219-0613","type":"print"},{"value":"1793-6691","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,20]]}}}