{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T05:40:57Z","timestamp":1742967657263,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030802226"},{"type":"electronic","value":"9783030802233"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-80223-3_13","type":"book-chapter","created":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T14:13:49Z","timestamp":1625148829000},"page":"188-206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving Non-uniform Planted and Filtered Random SAT Formulas Greedily"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0076-6308","authenticated-orcid":false,"given":"Tobias","family":"Friedrich","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2721-3618","authenticated-orcid":false,"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4133-2437","authenticated-orcid":false,"given":"Ralf","family":"Rothenberger","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1295-6715","authenticated-orcid":false,"given":"Andrew M.","family":"Sutton","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,2]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","unstructured":"Achlioptas, D., Jia, H., Moore, C.: Hiding satisfying assignments: two are better than one. J. Art. Int. Res. 24 (2005). https:\/\/doi.org\/10.1613\/jair.1681","DOI":"10.1613\/jair.1681"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Kirousis, L.M., Kranakis, E., Krizanc, D.: Rigorous results for random (2+p)-sat. Theor. Comput. Sci. 265(1\u20132), 109\u2013129 (2001)","DOI":"10.1016\/S0304-3975(01)00154-2"},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-319-08587-6_8","volume-title":"Automated Reasoning","author":"C Ans\u00f3tegui","year":"2014","unstructured":"Ans\u00f3tegui, C., Bonet, M.L., Gir\u00e1ldez-Cru, J., Levy, J.: The fractal dimension of SAT formulas. In: Demri, S., Kapur, D., Weidenbach, C. (eds.) IJCAR 2014. LNCS (LNAI), vol. 8562, pp. 107\u2013121. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-08587-6_8"},{"key":"13_CR4","doi-asserted-by":"publisher","unstructured":"Ans\u00f3tegui, C., Bonet, M.L., Gir\u00e1ldez-Cru, J., Levy, J.: On the classification of industrial SAT families. In: Armengol, E., Boixader, D., Grimaldo, F. (eds.) 18th International Conference Catalan Association for Artificial Intelligence. Frontiers in Artificial Intelligence and Applications, vol. 277, pp. 163\u2013172. IOS Press (2015). https:\/\/doi.org\/10.3233\/978-1-61499-578-4-163","DOI":"10.3233\/978-1-61499-578-4-163"},{"key":"13_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-642-04244-7_13","volume-title":"Principles and Practice of Constraint Programming","author":"C Ans\u00f3tegui","year":"2009","unstructured":"Ans\u00f3tegui, C., Bonet, M.L., Levy, J.: On the structure of industrial SAT instances. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 127\u2013141. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04244-7_13"},{"key":"13_CR6","unstructured":"Ans\u00f3tegui, C., Bonet, M.L., Levy, J.: Towards industrial-like random SAT instances. In: Boutilier, C. (ed.) 21st International Joint Conference Artificial Intelligence (IJCAI), pp. 387\u2013392 (2009). http:\/\/ijcai.org\/Proceedings\/09\/Papers\/072.pdf"},{"key":"13_CR7","unstructured":"Berthet, Q.: Optimal testing for planted satisfiability problems. CoRR abs\/1401.2205http:\/\/arxiv.org\/abs\/1401.2205 (2014)"},{"key":"13_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-030-17462-0_7","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"T Bl\u00e4sius","year":"2019","unstructured":"Bl\u00e4sius, T., Friedrich, T., Sutton, A.M.: On the empirical time complexity of scale-free 3-SAT at the phase transition. In: Vojnar, T., Zhang, L. (eds.) TACAS 2019. LNCS, vol. 11427, pp. 117\u2013134. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17462-0_7"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Boufkhad, Y., Dubois, O., Interian, Y., Selman, B.: Regular random k-sat: Properties of balanced formulas. J. Autom. Reasoning 35(1\u20133), 181\u2013200 (2005)","DOI":"10.1007\/s10817-005-9012-z"},{"key":"13_CR10","doi-asserted-by":"publisher","unstructured":"Bradonjic, M., Perkins, W.: On sharp thresholds in random geometric graphs. In: Jansen, K., Rolim, J.D.P., Devanur, N.R., Moore, C. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2014. LIPIcs, vol. 28, pp. 500\u2013514. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2014.500","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2014.500"},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-662-48054-0_15","volume-title":"Mathematical Foundations of Computer Science 2015","author":"AA Bulatov","year":"2015","unstructured":"Bulatov, A.A., Skvortsov, E.S.: Phase transition for local search on planted SAT. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 175\u2013186. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48054-0_15"},{"key":"13_CR12","unstructured":"Ans\u00f3tegui, C., Maria Luisa Bonet, J.L.: Scale-free random SAT instances. CoRR abs\/1708.06805http:\/\/arxiv.org\/abs\/1708.06805 (2017)"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Chao, M., Franco, J.V.: Probabilistic analysis of two heuristics for the 3-satisfiability problem. SIAM J. Comput. 15(4), 1106\u20131118 (1986)","DOI":"10.1137\/0215080"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Chao, M., Franco, J.V.: Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k satisfiability problem. Inf. Sci. 51(3), 289\u2013314 (1990)","DOI":"10.1016\/0020-0255(90)90030-E"},{"key":"13_CR15","doi-asserted-by":"publisher","unstructured":"Chv\u00e1tal, V., Reed, B.A.: Mick gets some (the odds are on his side). In: 33rd Symposium Foundations of Computer Science (FOCS), pp. 620\u2013627. IEEE Computer Society (1992). https:\/\/doi.org\/10.1109\/SFCS.1992.267789","DOI":"10.1109\/SFCS.1992.267789"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Szemer\u00e9di, E.: Many hard examples for resolution. J. ACM 35(4), 759\u2013768 (1988)","DOI":"10.1145\/48014.48016"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Wormald, N.: The number of satisfying assignments of random regular k-SAT formulas. Comb. Prob. Comput. 27(4), 496\u2013530 (2018)","DOI":"10.1017\/S0963548318000263"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Doerr, B., Neumann, F., Sutton, A.M.: Time complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulas. Algorithmica 78(2), 561\u2013586 (2017)","DOI":"10.1007\/s00453-016-0190-3"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Feige, U., Mossel, E., Vilenchik, D.: Complete convergence of message passing algorithms for some satisfiability problems. Theor. Comput. 9, 617\u2013651 (2013)","DOI":"10.4086\/toc.2013.v009a019"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Feldman, V., Perkins, W., Vempala, S.S.: On the complexity of random satisfiability problems with planted solutions. SIAM J. Comput. 47(4), 1294\u20131338 (2018)","DOI":"10.1137\/16M1078471"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Flaxman, A.: A spectral technique for random satisfiable 3CNF formulas. Random Struct. Algorithms 32(4), 519\u2013534 (2008)","DOI":"10.1002\/rsa.20213"},{"key":"13_CR22","unstructured":"Flaxman, A.D.: Average-case analysis for combinatorial problems. Ph.D. thesis, Carnegie Mellon University (May 2006)"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Franco, J., Paull, M.C.: Probabilistic analysis of the davis putnam procedure for solving the satisfiability problem. Discrete Appl. Math. 5(1), 77\u201387 (1983)","DOI":"10.1016\/0166-218X(83)90017-3"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Friedgut, E.: Sharp thresholds of graph properties, and the $$k$$-SAT problem. J. Amer. Math. Soc. 12(4), 1017\u20131054 (1999)","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"13_CR25","doi-asserted-by":"publisher","unstructured":"Friedrich, T., Krohmer, A., Rothenberger, R., Sauerwald, T., Sutton, A.M.: Bounds on the satisfiability threshold for power law distributed random SAT. In: Pruhs, K., Sohler, C. (eds.) 25th European Symposium on Algorithms (ESA). LIPIcs, vol. 87, pp. 37:1\u201337:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.37","DOI":"10.4230\/LIPIcs.ESA.2017.37"},{"key":"13_CR26","doi-asserted-by":"publisher","unstructured":"Friedrich, T., Rothenberger, R.: Sharpness of the satisfiability threshold for non-uniform random k-SAT. In: Kraus, S. (ed.) 28th International Joint Conference Artificial Intelligence (IJCAI), pp. 6151\u20136155. ijcai.org (2019). https:\/\/doi.org\/10.24963\/ijcai.2019\/853","DOI":"10.24963\/ijcai.2019\/853"},{"key":"13_CR27","doi-asserted-by":"crossref","unstructured":"Gir\u00e1ldez-Cru, J., Levy, J.: Generating SAT instances with community structure. Artif. Intell. 238, 119\u2013134 (2016)","DOI":"10.1016\/j.artint.2016.06.001"},{"key":"13_CR28","doi-asserted-by":"publisher","unstructured":"Gir\u00e1ldez-Cru, J., Levy, J.: Locality in random SAT instances. In: Sierra, C. (ed.) 26th International Joint Conference Artificial Intelligence (IJCAI), pp. 638\u2013644. ijcai.org (2017). https:\/\/doi.org\/10.24963\/ijcai.2017\/89","DOI":"10.24963\/ijcai.2017\/89"},{"key":"13_CR29","unstructured":"Hu, Y., Luo, W., Wang, J.: Community-based 3-sat formulas with a predefined solution. CoRR abs\/1902.09706, http:\/\/arxiv.org\/abs\/1902.09706 (2019)"},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E., Papadimitriou, C.H.: On the greedy algorithm for satisfiability. Inf. Process. Lett. 43(1), 53\u201355 (1992)","DOI":"10.1016\/0020-0190(92)90029-U"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Krivelevich, M., Vilenchik, D.: Solving random satisfiable 3CNF formulas in expected polynomial time. In: 17th Symposium Discrete Algorithms (SODA), pp. 454\u2013463. ACM Press (2006). http:\/\/dl.acm.org\/citation.cfm?id=1109557.1109608","DOI":"10.1145\/1109557.1109608"},{"key":"13_CR32","unstructured":"Mitchell, D.G., Selman, B., Levesque, H.J.: Hard and easy distributions of SAT problems. In: Swartout, W.R. (ed.) 10th Conference Artificial Intelligence (AAAI), pp. 459\u2013465. AAAI Press\/The MIT Press (1992). http:\/\/www.aaai.org\/Library\/AAAI\/1992\/aaai92-071.php"},{"key":"13_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-030-24258-9_4","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2019","author":"O Omelchenko","year":"2019","unstructured":"Omelchenko, O., Bulatov, A.A.: Satisfiability threshold for power law random 2-SAT in configuration model. In: Janota, M., Lynce, I. (eds.) SAT 2019. LNCS, vol. 11628, pp. 53\u201370. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-24258-9_4"},{"key":"13_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1007\/978-3-642-14186-7_22","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2010","author":"V Rathi","year":"2010","unstructured":"Rathi, V., Aurell, E., Rasmussen, L., Skoglund, M.: Bounds on threshold of regular random k-SAT. In: Strichman, O., Szeider, S. (eds.) SAT 2010. LNCS, vol. 6175, pp. 264\u2013277. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14186-7_22"},{"key":"13_CR35","doi-asserted-by":"crossref","unstructured":"Selman, B., Kirkpatrick, S.: Critical behavior in the computational cost of satisfiability testing. Artif. Intell. 81(1\u20132), 273\u2013295 (1996)","DOI":"10.1016\/0004-3702(95)00056-9"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2021"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-80223-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,1]],"date-time":"2021-07-01T23:29:45Z","timestamp":1625182185000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-80223-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030802226","9783030802233"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-80223-3_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"2 July 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Theory and Applications of Satisfiability Testing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Barcelona","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sat2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.iiia.csic.es\/sat2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}