{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:41:18Z","timestamp":1725745278614},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_34","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T09:17:34Z","timestamp":1376644654000},"page":"484-496","source":"Crossref","is-referenced-by-count":0,"title":["The Power of Choice for Random Satisfiability"],"prefix":"10.1007","author":[{"given":"Varsha","family":"Dani","sequence":"first","affiliation":[]},{"given":"Josep","family":"Diaz","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Hayes","sequence":"additional","affiliation":[]},{"given":"Cristopher","family":"Moore","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5920","key":"34_CR1","doi-asserted-by":"publisher","first-page":"1453","DOI":"10.1126\/science.1167782","volume":"323","author":"D. Achlioptas","year":"2009","unstructured":"Achlioptas, D., D\u2019Souza, R., Spencer, J.: Explosive percolation in random networks. Science\u00a0323(5920), 1453\u20131455 (2009)","journal-title":"Science"},{"key":"34_CR2","unstructured":"Achlioptas, D., Moore, C.: The asymptotic order of the random k-SAT threshold. In: Proc. 43rd Symposium on Foundations of Computer Science, pp. 779\u2013788 (2002)"},{"issue":"2","key":"34_CR3","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/S0022-0000(03)00120-X","volume":"67","author":"D. Achlioptas","year":"2003","unstructured":"Achlioptas, D., Moore, C.: Almost all graphs with average degree 4 are 3-colorable. Journal Computer System Science\u00a067(2), 441\u2013471 (2003)","journal-title":"Journal Computer System Science"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Peres, Y.: The threshold for random k-SAT is 2\n                    k\n                   (ln 2\u2009\u2212\u2009O(k)). In: Proc. 35th STOC, pp. 223\u2013231 (2003)","DOI":"10.1145\/780575.780577"},{"issue":"1","key":"34_CR5","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1002\/rsa.1019","volume":"19","author":"T. Bohman","year":"2001","unstructured":"Bohman, T., Frieze, A.: Avoiding a giant component. Random Struct. Algorithms\u00a019(1), 75\u201385 (2001)","journal-title":"Random Struct. Algorithms"},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1017\/S0963548306007486","volume":"15","author":"T. Bohman","year":"2006","unstructured":"Bohman, T., Kravitz, D.: Creating a giant component. Combinatorics, Probability and Computing\u00a015, 489\u2013511 (2006)","journal-title":"Combinatorics, Probability and Computing"},{"issue":"4","key":"34_CR7","doi-asserted-by":"publisher","first-page":"1106","DOI":"10.1137\/0215080","volume":"15","author":"M.-T. Chao","year":"1986","unstructured":"Chao, M.-T., Franco, J.V.: Probabilistic analysis of two heuristics for the 3-satisfiability problem. SIAM Journal on Computing\u00a015(4), 1106\u20131118 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR8","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","volume":"51","author":"M.-T. Chao","year":"1990","unstructured":"Chao, M.-T., Franco, J.V.: Probabilistic analysis of a generalization of the unit clause literal selection heuristic for the k-satisfiability problem. Information Science\u00a051, 289\u2013314 (1990)","journal-title":"Information Science"},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"Chvatal, V., Reed, B.: Mick Gets Some (the Odds Are on His Side). In: Proc. 33rd FOCS, pp. 620\u2013627 (1992)","DOI":"10.1109\/SFCS.1992.267789"},{"key":"34_CR10","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Panagiotou, K.: Going after the k-SAT Threshold. To appear in Proc. STOC (2013)","DOI":"10.1145\/2488608.2488698"},{"key":"34_CR11","doi-asserted-by":"publisher","first-page":"2920","DOI":"10.1016\/j.tcs.2009.02.020","volume":"410","author":"J. Diaz","year":"2009","unstructured":"Diaz, J., Kirousis, L., Mitsche, D., Perez, X.: On the satisfiability threshold of formulae with three literals per clause. Theoretical Computer Science\u00a0410, 2920\u20132934 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"34_CR12","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1006\/jagm.1997.0867","volume":"24","author":"O. Dubois","year":"1997","unstructured":"Dubois, O., Boufkhad, Y.: A general upper bound for the satisfiability threshold of random r-SAT formulae. Journal of Algorithms\u00a024(2), 395\u2013420 (1997)","journal-title":"Journal of Algorithms"},{"issue":"1-2","key":"34_CR13","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0304-3975(01)00156-6","volume":"265","author":"W. Fernandez de la Vega","year":"2001","unstructured":"Fernandez de la Vega, W.: Random 2-SAT: results and problems. Theoretical Computer Science\u00a0265(1-2), 131\u2013146 (2001)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"34_CR14","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/rsa.20070","volume":"27","author":"A. Flaxman","year":"2005","unstructured":"Flaxman, A., Gamarnik, D., Sorkin, G.: Embracing the giant component. Random Structures and Algorithms\u00a027(3), 277\u2013289 (2005)","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"34_CR15","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"Friedgut, E.: Sharp thresholds of graph properties, and the k-SAT problem. Journal of the American Mathematical Society\u00a012(4), 1017\u20131054 (1999); Appendix by Bourgain, J.","journal-title":"Journal of the American Mathematical Society"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"Goerdt, A.: A Threshold for Unsatisfiability. Journal of Computer and System Sciences, 469\u2013486 (1996)","DOI":"10.1006\/jcss.1996.0081"},{"key":"34_CR17","unstructured":"Taghi Hajiaghayi, M., Sorkin, G.: The satisfiability threshold of random 3-SAT is at least 3.52. IBM Research Report RC22942 (2003)"},{"key":"34_CR18","unstructured":"Kalapala, V., Moore, C.: The Phase Transition in Exact Cover. Chicago Journal of Theoretical Computer Science\u00a05 (2008)"},{"issue":"4","key":"34_CR19","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1002\/rsa.20104","volume":"28","author":"A. Kaporis","year":"2006","unstructured":"Kaporis, A., Kirousis, L., Lalas, E.: The probabilistic analysis of a greedy satisfiability algorithm. Random Struct. Algorithms\u00a028(4), 444\u2013480 (2006)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"34_CR20","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U","volume":"12","author":"L.M. Kirousis","year":"1998","unstructured":"Kirousis, L.M., Kranakis, E., Krizanc, D., Stamatiou, Y.C.: Approximating the unsatisfiability threshold of random formulas. Random Struct. Algorithms\u00a012(3), 253\u2013269 (1998)","journal-title":"Random Struct. Algorithms"},{"key":"34_CR21","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1002\/rsa.20090","volume":"28","author":"S. Mertens","year":"2006","unstructured":"Mertens, S., M\u00e9zard, M., Zecchina, R.: Threshold values of random K-SAT from the cavity method. Random Structures & Algorithms\u00a028, 340\u2013373 (2006)","journal-title":"Random Structures & Algorithms"},{"key":"34_CR22","doi-asserted-by":"crossref","unstructured":"Moore, C., Mertens, S.: The Nature of Computation. Oxford University Press (2011)","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001"},{"key":"34_CR23","doi-asserted-by":"crossref","unstructured":"Mezard, M., Montanari, A.: Information, Physics and Computation. Oxford Graduate Texts (2009)","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001"},{"key":"34_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1103\/PhysRevE.66.056126","volume":"66","author":"M. Mezard","year":"2002","unstructured":"Mezard, M., Zecchina, R.: Random K-satisfiability problem: From an analytic solution to an efficient algorithm. Physical Review E\u00a066, 056126, 1\u201326 (2002)","journal-title":"Physical Review E"},{"key":"34_CR25","unstructured":"Mitchell, D., Selman, B., Levesque, H.: Hard and easy distributions of SAT problems. In: Proc. 10th. National Conference on Artificial Intelligence (AAAI), pp. 459\u2013465 (1992)"},{"issue":"3","key":"34_CR26","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1239\/jap\/1285335410","volume":"47","author":"E. Mossel","year":"2010","unstructured":"Mossel, E., Sen, A.: Branching process approach for the 2-SAT threshold. Journal of Applied Probability\u00a047(3), 796\u2013810 (2010)","journal-title":"Journal of Applied Probability"},{"key":"34_CR27","unstructured":"Perkins, W.: Random K-SAT and the power of two choices. arXIv:1209.5313v1 (September 2012)"},{"issue":"4","key":"34_CR28","doi-asserted-by":"publisher","first-page":"1450","DOI":"10.1214\/11-AAP798","volume":"22","author":"O. Riordan","year":"2012","unstructured":"Riordan, O., Wanke, L.: Achlioptas process phase transition are continuous. Annals of Applied Probability\u00a022(4), 1450\u20131464 (2012)","journal-title":"Annals of Applied Probability"},{"key":"34_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1007\/978-3-642-15369-3_53","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Sinclair","year":"2010","unstructured":"Sinclair, A., Vilenchik, D.: Delaying Satisfiability for Random 2SAT. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX and RANDOM 2010. LNCS, vol.\u00a06302, pp. 710\u2013723. Springer, Heidelberg (2010)"},{"key":"34_CR30","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s00493-007-2163-2","volume":"27","author":"J. Spencer","year":"2007","unstructured":"Spencer, J., Wormald, N.: Birth Control for Giants. Combinatorica\u00a027, 587 (2007)","journal-title":"Combinatorica"},{"issue":"3-4","key":"34_CR31","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(99)00128-3","volume":"72","author":"N.C. Verhoeven","year":"2000","unstructured":"Verhoeven, N.C.: Random 2-SAT and unsatisfiability. Information Professing Letters\u00a072(3-4), 119\u2013124 (2000)","journal-title":"Information Professing Letters"},{"key":"34_CR32","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","volume":"5","author":"N.C. Wormald","year":"1995","unstructured":"Wormald, N.C.: Differential equations for random processes and random graphs. Annals of Applied Probability\u00a05, 1217\u20131235 (1995)","journal-title":"Annals of Applied Probability"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T13:55:39Z","timestamp":1558014939000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}