{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T03:55:01Z","timestamp":1725854101667},"publisher-location":"New York, NY","reference-count":15,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_423","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T19:32:23Z","timestamp":1553110343000},"page":"2236-2239","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Thresholds of Random k-Sat"],"prefix":"10.1007","author":[{"given":"Alexis","family":"Kaporis","sequence":"first","affiliation":[]},{"given":"Lefteris","family":"Kirousis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"issue":"1\u20132","key":"418_CR20175","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0304-3975(01)00159-1","volume":"265","author":"D Achlioptas","year":"2001","unstructured":"Achlioptas D (2001) Lower bounds for random 3-SAT via differential equations. Theor Comput Sci 265(1\u20132):159\u2013185","journal-title":"Theor Comput Sci"},{"key":"418_CR20176","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1109\/SFCS.2000.892327","volume-title":"41st annual symposium on foundations of computer science","author":"D Achlioptas","year":"2000","unstructured":"Achlioptas D, Sorkin GB (2000) Optimal myopic algorithms for random 3-SAT. In: 41st annual symposium on foundations of computer science, Redondo Beach. IEEE Computer Society, Washington, DC, pp\u00a0590\u2013600"},{"key":"418_CR20177","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1109\/SFCS.1992.267789","volume-title":"33rd annual symposium on foundations of computer science, Pittsburgh","author":"V Chv\u00e1tal","year":"1992","unstructured":"Chv\u00e1tal V, Reed B (1992) Mick gets some (the odds are on his side). In: 33rd annual symposium on foundations of computer science, Pittsburgh. IEEE Computer Society, pp\u00a0620\u2013627"},{"issue":"4","key":"418_CR20178","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M Davis","year":"1960","unstructured":"Davis M, Putnam H (1960) A computing procedure for quantification theory. J Assoc Comput Mach 7(4):201\u2013215","journal-title":"J Assoc Comput Mach"},{"key":"418_CR20179","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M Davis","year":"1962","unstructured":"Davis M, Logemann G, Loveland D (1962) A machine program for theoremproving. Commun ACM 5:394\u2013397","journal-title":"Commun ACM"},{"key":"418_CR20180","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0304-3975(01)00161-X","volume":"265","author":"O Dubois","year":"2001","unstructured":"Dubois O (2001) Upper bounds on the satisfiability threshold. Theor Comput Sci 265:187\u2013197","journal-title":"Theor Comput Sci"},{"key":"418_CR20181","first-page":"126","volume-title":"11th ACM-SIAM symposium on discrete algorithms","author":"O Dubois","year":"2000","unstructured":"Dubois O, Boufkhad Y, Mandler J (2000) Typical random 3-SAT formulae and the satisfiability threshold. In: 11th ACM-SIAM symposium on discrete algorithms, San Francisco. Society for Industrial and Applied Mathematics, pp\u00a0126\u2013127"},{"key":"418_CR20182","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/BF01874393","volume":"1","author":"J Franco","year":"1984","unstructured":"Franco J (1984) Probabilistic analysis of the pure literal heuristic for the satisfiability problem. Ann Oper Res 1:273\u2013289","journal-title":"Ann Oper Res"},{"key":"418_CR20183","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0304-3975(01)00158-X","volume":"265","author":"J Franco","year":"2001","unstructured":"Franco J (2001) Results related to threshold phenomena research in satisfiability: lower bounds. Theor Comput Sci 265:147\u2013157","journal-title":"Theor Comput Sci"},{"key":"418_CR20184","first-page":"1017","volume":"12","author":"E Friedgut","year":"1997","unstructured":"Friedgut E (1997) Sharp thresholds of graph properties, and the k-SAT problem. J AMS 12:1017\u20131054","journal-title":"J AMS"},{"key":"418_CR20185","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1006\/jcss.1996.0081","volume":"33","author":"A Goerdt","year":"1996","unstructured":"Goerdt A (1996) A threshold for unsatisfiability. J Comput Syst Sci 33:469\u2013486","journal-title":"J Comput Syst Sci"},{"issue":"4","key":"418_CR20186","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1002\/rsa.20104","volume":"28","author":"AC Kaporis","year":"2006","unstructured":"Kaporis AC, Kirousis LM, Lalas EG (2006) The probabilistic analysis of a greedy satisfiability algorithm. Random Struct Algorithms 28(4):444\u2013480","journal-title":"Random Struct Algorithms"},{"key":"418_CR20187","first-page":"159","volume-title":"Computational complexity and statistical physics","author":"L Kirousis","year":"2006","unstructured":"Kirousis L, Stamatiou Y, Zito M (2006) The unsatisfiability threshold conjecture: the techniques behind upper bound improvements. In: Percus A, Istrate G, Moore C (eds) Computational complexity and statistical physics. Santa Fe Institute studies in the sciences of complexity. Oxford University Press, New York, pp\u00a0159\u2013178"},{"key":"418_CR20188","first-page":"459","volume-title":"10th national conference on artificial intelligence","author":"D Mitchell","year":"1992","unstructured":"Mitchell D, Selman B, Levesque H (1992) Hard and easy distribution of SAT problems. In: 10th national conference on artificial intelligence, San Jose. AAAI Press, Menlo Park, pp\u00a0459\u2013465"},{"key":"418_CR20189","doi-asserted-by":"publisher","first-page":"1357","DOI":"10.1103\/PhysRevE.56.1357","volume":"56","author":"R Monasson","year":"1997","unstructured":"Monasson R, Zecchina R (1997) Statistical mechanics of the random k-SAT problem. Phys Rev E 56:1357\u20131361","journal-title":"Phys Rev E"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_423","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T20:20:25Z","timestamp":1553113225000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_423"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_423","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}