{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:59:06Z","timestamp":1764133146940,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["279611"],"award-info":[{"award-number":["279611"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["621-2012-5645"],"award-info":[{"award-number":["621-2012-5645"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["648276"],"award-info":[{"award-number":["648276"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188856","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"866-877","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Clique is hard on average for regular resolution"],"prefix":"10.1145","author":[{"given":"Albert","family":"Atserias","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Spain"}]},{"given":"Ilario","family":"Bonacina","sequence":"additional","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Spain"}]},{"given":"Susanna F.","family":"de Rezende","sequence":"additional","affiliation":[{"name":"KTH, Sweden"}]},{"given":"Massimo","family":"Lauria","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Italy"}]},{"given":"Jakob","family":"Nordstr\u00f6m","sequence":"additional","affiliation":[{"name":"KTH, Sweden"}]},{"given":"Alexander","family":"Razborov","sequence":"additional","affiliation":[{"name":"University of Chicago, USA \/ Russian Academy of Sciences, Russia"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"Noga Alon Michael Krivelevich and Benny Sudakov. 1998.  Noga Alon Michael Krivelevich and Benny Sudakov. 1998."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4%3C457::AID-RSA14%3E3.0.CO;2-W"},{"volume-title":"Proceedings of the 14th National Conference on Artificial Intelligence (AAAI \u201997)","author":"Bayardo Roberto J.","key":"e_1_3_2_2_3_1","unstructured":"Roberto J. Bayardo Jr . and Robert Schrag. 1997. Using CSP Look-Back Techniques to Solve Real-World SAT Instances . In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI \u201997) . 203\u2013208. Roberto J. Bayardo Jr. and Robert Schrag. 1997. Using CSP Look-Back Techniques to Solve Real-World SAT Instances. In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI \u201997). 203\u2013208."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0230-0"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875477"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499937.2499941"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2355580.2355582"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007391"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_3_2_2_11_1","unstructured":"Stefan S. Dantchev Barnaby Martin and Stefan Szeider. 2011.  Stefan S. Dantchev Barnaby Martin and Stefan Szeider. 2011."},{"key":"e_1_3_2_2_12_1","volume-title":"Computational Complexity 20 (March","author":"Complexity Parameterized Proof","year":"2011","unstructured":"Parameterized Proof Complexity . Computational Complexity 20 (March 2011 ), 51\u201385. Issue 1. Preliminary version in FOCS \u201907. Parameterized Proof Complexity. Computational Complexity 20 (March 2011), 51\u201385. Issue 1. Preliminary version in FOCS \u201907."},{"key":"e_1_3_2_2_13_1","volume-title":"Fellows","author":"Downey Rodney","year":"1995","unstructured":"Rodney Downey and Michael R . Fellows . 1995 . Rodney Downey and Michael R. Fellows. 1995."},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_3_2_2_15_1","unstructured":"Armin Haken. 1985.  Armin Haken. 1985."},{"key":"e_1_3_2_2_16_1","volume-title":"Theoretical Computer Science 39, 2-3 (Aug","author":"Resolution The Intractability","year":"1985","unstructured":"The Intractability of Resolution . Theoretical Computer Science 39, 2-3 (Aug . 1985 ), 297\u2013308. The Intractability of Resolution. Theoretical Computer Science 39, 2-3 (Aug. 1985), 297\u2013308."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","key":"e_1_3_2_2_19_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_3_2_2_20_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_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.37236\/1193"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275541"},{"key":"e_1_3_2_2_23_1","unstructured":"Jan Kraj\u00ed\u010dek. 1995.  Jan Kraj\u00ed\u010dek. 1995."},{"volume-title":"Propositional Logic, and Complexity Theory","author":"Arithmetic Bounded","key":"e_1_3_2_2_24_1","unstructured":"Bounded Arithmetic , Propositional Logic, and Complexity Theory . Cambridge University Press , New York . Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press, New York."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3193-9"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1055985"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.769433"},{"key":"e_1_3_2_2_29_1","unstructured":"Ciaran McCreesh. 2017.  Ciaran McCreesh. 2017."},{"key":"e_1_3_2_2_30_1","unstructured":"Solving Hard Subgraph Problems in Parallel. Ph.D. Dissertation. University of Glasgow.  Solving Hard Subgraph Problems in Parallel. Ph.D. Dissertation. University of Glasgow."},{"key":"e_1_3_2_2_31_1","unstructured":"Matthew W. Moskewicz Conor F. Madigan Ying Zhao Lintao Zhang and Sharad Malik. 2001.  Matthew W. Moskewicz Conor F. Madigan Ying Zhao Lintao Zhang and Sharad Malik. 2001."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379017"},{"key":"e_1_3_2_2_33_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 . Commentationes Mathematicae Universitatis Carolinae 026 , 2 (1985), 415 \u2013 419 . Jaroslav Ne\u0161et\u0159il and Svatopluk Poljak. 1985. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 026, 2 (1985), 415\u2013419.","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.3390\/a5040545"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275583"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-002-0007-7"},{"key":"e_1_3_2_2_37_1","unstructured":"Benjamin Rossman. 2008.  Benjamin Rossman. 2008."},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374480"},{"key":"e_1_3_2_2_39_1","unstructured":"Benjamin Rossman. 2010.  Benjamin Rossman. 2010."},{"key":"e_1_3_2_2_40_1","unstructured":"Average-Case Complexity of Detecting Cliques. Ph.D. Dissertation. Masschussets Institute of Technology.  Average-Case Complexity of Detecting Cliques. Ph.D. Dissertation. Masschussets Institute of Technology."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839059"},{"key":"e_1_3_2_2_42_1","unstructured":"Virginia Vassilevska. 2009.  Virginia Vassilevska. 2009."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.10.014"},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Los Angeles CA USA","acronym":"STOC '18"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188856","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:09Z","timestamp":1750212429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188856"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":44,"alternative-id":["10.1145\/3188745.3188856","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188856","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}