{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:28Z","timestamp":1750220968288,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T00:00:00Z","timestamp":1563580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC Advanced","award":["339691 (FEALORA)"],"award-info":[{"award-number":["339691 (FEALORA)"]}]},{"DOI":"10.13039\/501100006475","name":"Bergen Research Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            We introduce the notion of monotone linear programming circuits (MLP circuits), a model of computation for partial Boolean functions. Using this model, we prove the following results.\n            <jats:sup>1<\/jats:sup>\n          <\/jats:p>\n          <jats:p>(1) MLP circuits are superpolynomially stronger than monotone Boolean circuits.<\/jats:p>\n          <jats:p>(2) MLP circuits are exponentially stronger than monotone span programs over the reals.<\/jats:p>\n          <jats:p>(3) MLP circuits can be used to provide monotone feasibility interpolation theorems for Lov\u00e1sz-Schrijver proof systems and for mixed Lov\u00e1sz-Schrijver proof systems.<\/jats:p>\n          <jats:p>(4) The Lov\u00e1sz-Schrijver proof system cannot be polynomially simulated by the cutting planes proof system.<\/jats:p>\n          <jats:p>Finally, we establish connections between the problem of proving lower bounds for the size of MLP circuits and the field of extension complexity of polytopes.<\/jats:p>","DOI":"10.1145\/3337787","type":"journal-article","created":{"date-parts":[[2019,7,22]],"date-time":"2019-07-22T12:15:03Z","timestamp":1563797703000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Representations of Monotone Boolean Functions by Linear Programs"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7798-7446","authenticated-orcid":false,"given":"Mateus De Oliveira","family":"Oliveira","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}]},{"given":"Pavel","family":"Pudl\u00e1k","sequence":"additional","affiliation":[{"name":"Czech Academy of Sciences, Czech Republic"}]}],"member":"320","published-online":{"date-parts":[[2019,7,20]]},"reference":[{"volume-title":"Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS\u201902)","author":"Alekhnovich Michael","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050058"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-73.1.1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275569"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2014.0694"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488629"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1585"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 32nd Computational Complexity Conference (CCC\u201917)","volume":"79","author":"de Oliveira Oliveira Mateus","year":"2017"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2716307"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of a DIMACS Workshop","volume":"39","author":"Fu Xudong","year":"1998"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370100001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00334-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0757-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/646516.759239"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1617"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050024"},{"volume-title":"Proceedings of the 8th Annual Structure in Complexity Theory Conference. IEEE Comput. Soc. Press","author":"Karchmer M.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_29"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275541"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/1521-3870(200211)48:4<602::AID-MALQ602>3.0.CO;2-J"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/100816833"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275583"},{"key":"e_1_2_1_26_1","volume-title":"Barry Cooper and John K. Truss (Eds.)","volume":"258","author":"Pudl\u00e1k Pavel","year":"1999"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/039\/15"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01157687"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1090\/trans2\/147\/08"},{"key":"e_1_2_1_31_1","first-page":"201","article-title":"Unprovability of circuit size lower bounds in certain fragments of bounded arithmetic","volume":"59","author":"Razborov Alexander A.","year":"1995","journal-title":"Izvest. RAN"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2951860.2951875"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.51"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591834"},{"volume-title":"Combinatorial Optimization: Polyhedra and Efficiency.","year":"2003","author":"Schrijver Alexander","key":"e_1_2_1_35_1"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3337787","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3337787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:25Z","timestamp":1750204465000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3337787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,20]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3337787"],"URL":"https:\/\/doi.org\/10.1145\/3337787","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,7,20]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}