{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T05:06:07Z","timestamp":1777957567452,"version":"3.51.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T00:00:00Z","timestamp":1710374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000925","name":"John Templeton Foundation","doi-asserted-by":"crossref","award":["60842"],"award-info":[{"award-number":["60842"]}],"id":[{"id":"10.13039\/100000925","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DFG","award":["BE 4209\/3-1"],"award-info":[{"award-number":["BE 4209\/3-1"]}]},{"DOI":"10.13039\/100007569","name":"Carl Zeiss Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007569","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund FWF","doi-asserted-by":"crossref","award":["J-4361"],"award-info":[{"award-number":["J-4361"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DAAD\/DST"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            We prove the first genuine quantified Boolean formula (QBF) proof size lower bounds for the proof system Merge Resolution (MRes), a refutational proof system for prenex QBFs with a CNF matrix. Unlike most QBF resolution systems in the literature, proofs in MRes consist of resolution steps\n            <jats:italic>together<\/jats:italic>\n            with information on countermodels, which are syntactically stored in the proofs as merge maps. This makes MRes quite powerful: it has strategy extraction by design and allows short proofs for formulas that are hard for classical QBF resolution systems.\n          <\/jats:p>\n          <jats:p>\n            Here, we show the first genuine QBF\n            <jats:italic>exponential lower bounds for MRes<\/jats:italic>\n            , thereby uncovering limitations of MRes. Technically, the results are either transferred from bounds from circuit complexity (for restricted versions of MRes) or directly obtained by combinatorial arguments (for full MRes). Our results imply that the MRes approach is\n            <jats:italic>largely orthogonal to other QBF resolution models<\/jats:italic>\n            such as the QCDCL resolution systems QRes and QURes and the expansion systems \u2200 Exp + Res and IR.\n          <\/jats:p>","DOI":"10.1145\/3638263","type":"journal-article","created":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T11:30:26Z","timestamp":1703244626000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Hard QBFs for Merge Resolution"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2870-1648","authenticated-orcid":false,"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t Jena, Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7452-6521","authenticated-orcid":false,"given":"Joshua","family":"Blinkhorn","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t Jena, Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9116-4398","authenticated-orcid":false,"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences (CI of Homi Bhabha National Institute), Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7799-1568","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Peitl","sequence":"additional","affiliation":[{"name":"Institute of Logic and Computation, TU Wien, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6501-6589","authenticated-orcid":false,"given":"Gaurav","family":"Sood","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences (CI of Homi Bhabha National Institute), Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,14]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-012-0152-6"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09284-3_12"},{"key":"e_1_3_3_4_2","first-page":"353","volume-title":"Mathematics for Computation (M4C)","author":"Beyersdorff Olaf","year":"2022","unstructured":"Olaf Beyersdorff. 2022. Proof complexity of quantified Boolean logic \u2013 a survey. In Mathematics for Computation (M4C), Marco Benini, Olaf Beyersdorff, Michael Rathjen, and Peter Schuster (Eds.). World Scientific, Singapore, 353\u2013391."},{"key":"e_1_3_3_5_2","article-title":"Formulas with large weight: A new technique for genuine QBF lower bounds","volume":"24","author":"Beyersdorff Olaf","year":"2017","unstructured":"Olaf Beyersdorff and Joshua Blinkhorn. 2017. Formulas with large weight: A new technique for genuine QBF lower bounds. Electron. Colloquium Comput. Complex. 24 (2017), 32.","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09940-0"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.23638\/LMCS-15(1:13)2019"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-020-09560-1"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3565286"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2020.12"},{"issue":"2","key":"e_1_3_3_11_2","article-title":"Understanding the relative strength of QBF CDCL solvers and QBF resolution","volume":"19","author":"Beyersdorff Olaf","year":"2023","unstructured":"Olaf Beyersdorff and Benjamin B\u00f6hm. 2023. Understanding the relative strength of QBF CDCL solvers and QBF resolution. Log. Methods Comput. Sci. 19, 2 (2023).","journal-title":"Log. Methods Comput. Sci."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840740"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3381881"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3352155"},{"key":"e_1_3_3_15_2","article-title":"Feasible interpolation for QBF resolution calculi","volume":"13","author":"Beyersdorff Olaf","year":"2017","unstructured":"Olaf Beyersdorff, Leroy Chew, Meena Mahajan, and Anil Shukla. 2017. Feasible interpolation for QBF resolution calculi. Logical Methods in Computer Science 13 (2017). Issue 2.","journal-title":"Logical Methods in Computer Science"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2018.08.002"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.11.011"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3378665"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.3233\/FAIA201015"},{"key":"e_1_3_3_20_2","first-page":"28","volume-title":"20th International Conferences on Logic for Programming, Artificial Intelligence and Reasoning, LPAR 2015 (EPiC Series in Computing)","volume":"35","author":"Bj\u00f8rner Nikolaj","year":"2015","unstructured":"Nikolaj Bj\u00f8rner, Mikol\u00e1s Janota, and William Klieber. 2015. On conflicts and strategies in QBF. In 20th International Conferences on Logic for Programming, Artificial Intelligence and Reasoning, LPAR 2015 (EPiC Series in Computing), Ansgar Fehnker, Annabelle McIver, Geoff Sutcliffe, and Andrei Voronkov (Eds.), Vol. 35. EasyChair, 28\u201341."},{"key":"e_1_3_3_21_2","volume-title":"Canonical Expressions in Boolean Algebra","author":"Blake A.","year":"1937","unstructured":"A. Blake. 1937. Canonical Expressions in Boolean Algebra. Ph.D. Dissertation. University of Chicago."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-80223-3_4"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.09.009"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2023.21"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2022.22"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45221-5_21"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08587-6_7"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40970-2_25"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.01.048"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.07.009"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1025"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40970-2_27"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.11.017"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SAT.2022.22"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815493.2815497"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-018-9467-3"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-24258-9_23"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2019.04.002"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321253"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2019.00020"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.10.020"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-81955-1_28"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33558-7_47"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774637"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3638263","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3638263","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:53:35Z","timestamp":1750287215000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3638263"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,14]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3638263"],"URL":"https:\/\/doi.org\/10.1145\/3638263","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,14]]},"assertion":[{"value":"2020-12-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}