{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:46:01Z","timestamp":1725493561677},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_26","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"310-321","source":"Crossref","is-referenced-by-count":7,"title":["Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently"],"prefix":"10.1007","author":[{"given":"Joel","family":"Friedman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Goerdt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Dimitris Achlioptas. Setting 2 variables at a time yields a new lower bound for random 3-SAT. In Proceedings SToC 2000.","DOI":"10.1145\/335305.335309"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Dimitris Achlioptas, Ehud Friedgut. A threshold for random k-colourability. Random Structures and Algorithms 1999.","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<63::AID-RSA3>3.0.CO;2-7"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"Noga Alon, Nabil Kahale. A spectral technique for colouring random 3-colourable graphs (preliminary version). In Proceedings SToC 1994. ACM. 346\u2013355.","DOI":"10.1145\/195058.195187"},{"key":"26_CR4","unstructured":"Noga Alon, Joel H. Spencer. The probabilistic method. Wiley & Sons Inc. 1992."},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"Paul Beame, Richard Karp, Toniann Pitassi, Michael Saks. On the complexity of unsatisfiability proofs for random k-CNF formulas. 1997.","DOI":"10.1145\/276698.276870"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Paul Beame, Toniann Pitassi. Simplified and improved resolution lower bounds. In Proceedings FoCS 1996. IEEE. 274\u2013282.","DOI":"10.1109\/SFCS.1996.548486"},{"key":"26_CR7","unstructured":"Bela Bollobas. Random Graphs. Academic Press. 1985."},{"key":"26_CR8","unstructured":"Fan R. K. Chung. Spectral Graph Theory. American Mathematical Society. 1997."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Vasek Chvatal, Bruce Reed. Mick gets some (the odds are on his side). In Proceedings 33nd FoCS 1992. IEEE. 620\u2013627.","DOI":"10.1109\/SFCS.1992.267789"},{"issue":"4","key":"26_CR10","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chvatal","year":"1988","unstructured":"Vasek Chvatal, Endre Szemeredi. Many hard examples for resolution. Journal of the ACM 35(4), 1988, 759\u2013768.","journal-title":"Journal of the ACM"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"J. M. Crawford, L. D. Auton. Experimental results on the crossover point in random 3SAT. Artificial Intelligence 81, 1996.","DOI":"10.1016\/0004-3702(95)00046-1"},{"key":"26_CR12","unstructured":"Joel Friedman. Combinatorica, 1991."},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"Ehud Friedgut. Necessary and sufficient conditions for sharp thresholds of graph properties and the k-SAT problem. Journal of the American Mathematical Society 12, 1999, 1017\u20131054.","journal-title":"Journal of the American Mathematical Society"},{"issue":"2","key":"26_CR14","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1006\/jagm.1996.0016","volume":"20","author":"A. M. Frieze","year":"1996","unstructured":"Alan M. Frieze, Stephen Suen. Analysis of two simple heuristics on a random instance of k-SAT. Journal of Algorithms 20(2), 1996, 312\u2013355.","journal-title":"Journal of Algorithms"},{"key":"26_CR15","unstructured":"Xudong Fu. The complexity of the resolution proofs for the random set of clauses. Computational Complexity, 1998."},{"key":"26_CR16","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1006\/jcss.1996.0081","volume":"53","author":"A. Goerdt","year":"1996","unstructured":"Andreas Goerdt. A threshold for unsatisfiability. Journal of Computer and System Sciences 53, 1996, 469\u2013486.","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR17","series-title":"Lect Notes Comput Sci","volume-title":"Proceedings STACS 2001","author":"A. Goerdt","year":"2001","unstructured":"Andreas Goerdt, Michael Krivelevich. Efficient recognition of random unsatisfiable k-SAT instances by spectral methods. In Proceedings STACS 2001. LNCS."},{"key":"26_CR18","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s001459900012","volume":"9","author":"R. Impagliazzo","year":"1996","unstructured":"Russel Impagliazzo, Moni Naor. Efficient cryptographic schemes provably as secure as subset sum. Journal of cryptology 9, 1996, 199\u2013216.","journal-title":"Journal of cryptology"},{"issue":"3","key":"26_CR19","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":"Lefteris M. Kirousis, Evangelos Kranakis, Danny Krizanc, Yiannis Stamatiou. Approximating the unsatisfiability threshold of random formulas. Random Structures and Algorithms 12(3), 1998, 253\u2013269.","journal-title":"Random Structures and Algorithms"},{"key":"26_CR20","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0012-365X(89)90214-8","volume":"74","author":"A. D. Petford","year":"1989","unstructured":"A. D. Petford, Dominic Welsh. A randomised 3-colouring algorithm. Discrete Mathematics 74, 1989, 253\u2013261.","journal-title":"Discrete Mathematics"},{"key":"26_CR21","unstructured":"Uwe Sch\u00f6ning. Logic for Computer Science. Birkh\u00e4user."},{"issue":"1-2","key":"26_CR22","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0004-3702(95)00045-3","volume":"81","author":"B. Selman","year":"1996","unstructured":"Bart Selman, David G. Mitchell, Hector J. Levesque. Generating hard satisfiability problems. Artificial Intelligence 81(1-2), 1996, 17\u201329.","journal-title":"Artificial Intelligence"},{"key":"26_CR23","volume-title":"Linear Algebra and its Applications","author":"G. Strang","year":"1988","unstructured":"Gilbert Strang. Linear Algebra and its Applications. Harcourt Brace Jovanovich, Publishers, San Diego. 1988."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T22:28:47Z","timestamp":1556922527000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_26","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}