{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:56Z","timestamp":1750220636385,"version":"3.41.0"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>\n            We prove that for\n            <jats:italic>k<\/jats:italic>\n            \u226a 4\u221a\n            <jats:italic>n<\/jats:italic>\n            regular resolution requires length\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u03a9(\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            to establish that an Erd\u0151s\u2013R\u00e9nyi graph with appropriately chosen edge density does not contain a\n            <jats:italic>k<\/jats:italic>\n            -clique. This lower bound is optimal up to the multiplicative constant in the exponent and also implies unconditional\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u03a9(\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.\n          <\/jats:p>","DOI":"10.1145\/3449352","type":"journal-article","created":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T19:11:05Z","timestamp":1625080265000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Clique Is Hard on Average for Regular Resolution"],"prefix":"10.1145","volume":"68","author":[{"given":"Albert","family":"Atserias","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5697-8070","authenticated-orcid":false,"given":"Ilario","family":"Bonacina","sequence":"additional","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}]},{"given":"Susanna F.","family":"De Rezende","sequence":"additional","affiliation":[{"name":"Institute of Mathematics of the Czech Academy of Sciences, Czech Republic"}]},{"given":"Massimo","family":"Lauria","sequence":"additional","affiliation":[{"name":"Sapienza - Universit\u00e0 di Roma, Roma, Italy"}]},{"given":"Jakob","family":"Nordstr\u00f6m","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark and Lund University, Sweden"}]},{"given":"Alexander","family":"Razborov","sequence":"additional","affiliation":[{"name":"University of Chicago, USA, and Steklov Mathematical Institute, Moscow, Russia"}]}],"member":"320","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/302908.303020"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188856"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1867406.1867438"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/130914085"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0230-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875477"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499937.2499941"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2355580.2355582"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100053056"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13173-011-0050-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90057-C"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920)","volume":"12118","author":"Cavalar Bruno Pasqualotto","year":"2020","unstructured":"Bruno Pasqualotto Cavalar , Mrinal Kumar , and Benjamin Rossman . 2020 . Monotone circuit lower bounds from robust sunflowers . In Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920) , Lecture Notes in Computer Science , Vol. 12118 . 311\u2013322. Bruno Pasqualotto Cavalar, Mrinal Kumar, and Benjamin Rossman. 2020. Monotone circuit lower bounds from robust sunflowers. In Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920), Lecture Notes in Computer Science, Vol. 12118. 311\u2013322."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007391"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2019.6"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920)","volume":"12118","author":"Dantchev Stefan","year":"2020","unstructured":"Stefan Dantchev , Abdul Ghani , and Barnaby Martin . 2020 . Sherali-Adams and the binary encoding of combinatorial principles . In Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920) , Lecture Notes in Computer Science , Vol. 12118 . 336\u2013347. Stefan Dantchev, Abdul Ghani, and Barnaby Martin. 2020. Sherali-Adams and the binary encoding of combinatorial principles. In Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920), Lecture Notes in Computer Science, Vol. 12118. 336\u2013347."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0001-1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740816"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/911574"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","key":"e_1_2_1_26_1","unstructured":"Richard M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations . Springer , 85\u2013103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Springer, 85\u2013103."},{"volume-title":"Algorithms and Complexity: New Directions and Recent Results","author":"Karp Richard M.","key":"e_1_2_1_27_1","unstructured":"Richard M. Karp . 1976. The probabilistic analysis of some combinatorial search algorithms . In Algorithms and Complexity: New Directions and Recent Results . Academic Press , New York , 1\u201319. Richard M. Karp. 1976. The probabilistic analysis of some combinatorial search algorithms. In Algorithms and Complexity: New Directions and Recent Results. Academic Press, New York, 1\u201319."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/892533"},{"key":"e_1_2_1_29_1","first-page":"569","article-title":"An improved branch and bound algorithm for the maximum clique problem","volume":"58","author":"Konc Janez","year":"2007","unstructured":"Janez Konc and Du\u0161anka Jane\u017ei\u010d . 2007 . An improved branch and bound algorithm for the maximum clique problem . MATCH Commun. Math. Comput. Chem. 58 , 3 (2007), 569 \u2013 590 . Janez Konc and Du\u0161anka Jane\u017ei\u010d. 2007. An improved branch and bound algorithm for the maximum clique problem. MATCH Commun. Math. Comput. Chem. 58, 3 (2007), 569\u2013590.","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275541"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/225488"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.03.001"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3193-9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.769433"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379017"},{"key":"e_1_2_1_39_1","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"026","author":"Ne\u0161et\u0159il Jaroslav","year":"1985","unstructured":"Jaroslav Ne\u0161et\u0159il and Svatopluk Poljak . 1985 . On the complexity of the subgraph problem . Comment. Math. Univ. Carolin. 026 , 2 (1985), 415 \u2013 419 . Jaroslav Ne\u0161et\u0159il and Svatopluk Poljak. 1985. On the complexity of the subgraph problem. Comment. Math. Univ. Carolin. 026, 2 (1985), 415\u2013419.","journal-title":"Comment. Math. Univ. Carolin."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00290-6"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 16th International Computer Science Symposium in Russia (CSR'21)","author":"Pang Shuo","year":"2019","unstructured":"Shuo Pang . 2019 . Large clique is hard on average for resolution . In Proceedings of the 16th International Computer Science Symposium in Russia (CSR'21) . https:\/\/eccc.weizmann.ac.il\/report\/2019\/068 Shuo Pang. 2019. Large clique is hard on average for resolution. In Proceedings of the 16th International Computer Science Symposium in Russia (CSR'21). https:\/\/eccc.weizmann.ac.il\/report\/2019\/068"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1999.2972"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.3390\/a5040545"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275583"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-002-0007-7"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374480"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839059"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09584-4_12"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10489-016-0796-9"},{"key":"e_1_2_1_52_1","first-page":"3","article-title":"An improved bit parallel exact maximum clique algorithm","volume":"7","author":"Segundo Pablo San","year":"2013","unstructured":"Pablo San Segundo , Fernando Matia , Diego Rodr\u00edguez-Losada , and Miguel Hernando . 2013 . An improved bit parallel exact maximum clique algorithm . Optimiz. Lett. 7 , 3 (Mar. 2013), 467\u2013479. Pablo San Segundo, Fernando Matia, Diego Rodr\u00edguez-Losada, and Miguel Hernando. 2013. An improved bit parallel exact maximum clique algorithm. Optimiz. Lett. 7, 3 (Mar. 2013), 467\u2013479.","journal-title":"Optimiz. Lett."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.07.019"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2010.58"},{"key":"e_1_2_1_55_1","volume-title":"Stein et\u00a0al","author":"A.","year":"2017","unstructured":"W.\u00a0 A. Stein et\u00a0al . 2017 . Sage Mathematics Software (Version 8.1). The Sage Development Team . W.\u00a0A. Stein et\u00a0al. 2017. Sage Mathematics Software (Version 8.1). The Sage Development Team."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-006-9039-7"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783712.1783736"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11440-3_18"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-39817-4_21"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.10.014"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00054-0"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3449352","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3449352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:55Z","timestamp":1750197715000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3449352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":58,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1145\/3449352"],"URL":"https:\/\/doi.org\/10.1145\/3449352","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2020-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}