{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T11:48:27Z","timestamp":1763466507073,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T00:00:00Z","timestamp":1375315200000},"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":"publisher","id":[{"id":"10.13039\/100000925","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001655","name":"German Academic Exchange Service","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2013,8]]},"abstract":"<jats:p>\n            We study the performance of DPLL algorithms on parameterized problems. In particular, we investigate how difficult it is to decide whether small solutions exist for satisfiability and other combinatorial problems. For this purpose we develop a Prover-Delayer game that models the running time of DPLL procedures and we establish an information-theoretic method to obtain lower bounds to the running time of parameterized DPLL procedures. We illustrate this technique by showing lower bounds to the parameterized pigeonhole principle and to the ordering principle. As our main application we study the DPLL procedure for the problem of deciding whether a graph has a small clique. We show that proving the absence of a\n            <jats:italic>k<\/jats:italic>\n            -clique requires\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03a9(k)<\/jats:sup>\n            steps for a nontrivial distribution of graphs close to the critical threshold. For the restricted case of tree-like Parameterized Resolution, this result answers a question asked by Beyersdorff et al. [2012] of understanding the Resolution complexity of this family of formulas.\n          <\/jats:p>","DOI":"10.1145\/2499937.2499941","type":"journal-article","created":{"date-parts":[[2013,9,3]],"date-time":"2013-09-03T11:57:11Z","timestamp":1378209431000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Parameterized Complexity of DPLL Search Procedures"],"prefix":"10.1145","volume":"14","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[{"name":"University of Leeds and Sapienza University of Rome"}]},{"given":"Nicola","family":"Galesi","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome"}]},{"given":"Massimo","family":"Lauria","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2013,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/06066850X"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a005"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0288-y"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2016945.2016955"},{"volume-title":"Proceedings of the 37th IEEE Symposium on the Foundations of Computer Science. 274--282","author":"Beame P.","key":"e_1_2_1_5_1","unstructured":"Beame , P. and Pitassi , T . 1996. Simplified and improved resolution lower bounds . In Proceedings of the 37th IEEE Symposium on the Foundations of Computer Science. 274--282 . Beame, P. and Pitassi, T. 1996. Simplified and improved resolution lower bounds. In Proceedings of the 37th IEEE Symposium on the Foundations of Computer Science. 274--282."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369156"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1410"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0230-0"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-73.1.1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0036-5"},{"key":"e_1_2_1_12_1","unstructured":"Beyersdorff O. Galesi N. and Lauria M. 2010a. Hardness of parameterized resolution. Tech. rep. TR10-059 Electronic Colloquium on Computational Complexity.  Beyersdorff O. Galesi N. and Lauria M. 2010a. Hardness of parameterized resolution. Tech. rep. TR10-059 Electronic Colloquium on Computational Complexity."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.09.007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2023474.2023479"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2355580.2355582"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370100000"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799352474"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/647847.736889"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2007.09.003"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.52"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0001-1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/321033.321034"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer.   Downey R. G. and Fellows M. R. 1999. Parameterized Complexity . Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Dubhashi D. P. and Panconesi A. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.   Dubhashi D. P. and Panconesi A. 2009. Concentration of Measure for the Analysis of Randomized Algorithms . Cambridge University Press.","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.2921"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00345-4"},{"key":"e_1_2_1_31_1","unstructured":"Flum J. and Grohe M. 2006. Parameterized Complexity Theory. Springer.   Flum J. and Grohe M. 2006. Parameterized Complexity Theory . Springer."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2009.06.005"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Janson S. \u0141uczak T. and Ruci\u0144ski A. 2000. Random Graphs. Wiley.  Janson S. \u0141uczak T. and Ruci\u0144ski A. 2000. Random Graphs . Wiley.","DOI":"10.1002\/9781118032718"},{"volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications","author":"Niedermeier R.","key":"e_1_2_1_35_1","unstructured":"Niedermeier , R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications , Oxford University Press . Niedermeier, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press."},{"volume-title":"Proceedings of the 11th Symposium on Discrete Algorithms. 128--136","author":"Pudl\u00e1k P.","key":"e_1_2_1_36_1","unstructured":"Pudl\u00e1k , P. and Impagliazzo , R . 2000. A lower bound for DLL algorithms for SAT . In Proceedings of the 11th Symposium on Discrete Algorithms. 128--136 . Pudl\u00e1k, P. and Impagliazzo, R. 2000. A lower bound for DLL algorithms for SAT. In Proceedings of the 11th Symposium on Discrete Algorithms. 128--136."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321253"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374480"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.26"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2178\/bsl\/1203350879"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703428555"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050044"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.8928"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499937.2499941","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2499937.2499941","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:00Z","timestamp":1750232040000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499937.2499941"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["10.1145\/2499937.2499941"],"URL":"https:\/\/doi.org\/10.1145\/2499937.2499941","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2013,8]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}