{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T19:47:12Z","timestamp":1720640832524},"reference-count":11,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2003,10,1]],"date-time":"2003-10-01T00:00:00Z","timestamp":1064966400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electronic Notes in Discrete Mathematics"],"published-print":{"date-parts":[[2003,10]]},"DOI":"10.1016\/s1571-0653(04)00461-5","type":"journal-article","created":{"date-parts":[[2004,10,24]],"date-time":"2004-10-24T03:07:12Z","timestamp":1098587232000},"page":"21-46","source":"Crossref","is-referenced-by-count":13,"special_numbering":"C","title":["Recognizing more random unsatisfiable 3-SAT instances efficiently"],"prefix":"10.1016","volume":"16","author":[{"given":"Andreas","family":"Goerdt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Lanka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB1","doi-asserted-by":"crossref","unstructured":"Fan R. K. Chung. Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, Vol. 92. American Mathematical Society, Providence, R. I.,1997.","DOI":"10.1090\/cbms\/092"},{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB2","doi-asserted-by":"crossref","unstructured":"A. Coja-Oghlan, A. Goerdt, A. Lanka, F. Sch\u00e4dlich. Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques. In Proceedings FCT 2003. To appear.","DOI":"10.1007\/978-3-540-45077-1_3"},{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB3","doi-asserted-by":"crossref","unstructured":"U. Feige. Relations between average case complexity and approximation complexity. In Proceedings STOC 2002.","DOI":"10.1145\/509907.509985"},{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB4","unstructured":"U. Feige, E. Ofek. Spectral Techniques Applied to Sparse Random Graphs. 2003. Available at http:\/\/wisdomarchive.wisdom.weizmann.ac.il:81\/archive\/00000307\/"},{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB5","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","article-title":"Necessary and Sufficient Conditions for Sharp Thresholds of Graph Properties and the k-SAT problem","volume":"12","author":"Friedgut","year":"1999","journal-title":"Journal of the American Mathematical Society"},{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB6","first-page":"310","article-title":"Recognizing more Unsatisfiable Random 3-Sat Instances efficiently","author":"Friedman","year":"2001","journal-title":"Proceedings ICALP"},{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB7","first-page":"587","article-title":"On the second Eigenvalue in Random Regular Graphs","author":"Friedman","year":"1989","journal-title":"Proceedings STOC"},{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB8","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1007\/BF02579329","article-title":"The Eigenvalues of Random Symmetric Matrices","volume":"1","author":"F\u00fcredi","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB9","first-page":"280","article-title":"Some Results on Random Unsatisfiable k-SAT Instances and Approximation Algorithms Applied to Random Structures","author":"Goerdt","year":"2002","journal-title":"Proceedings MFCS"},{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB10","first-page":"294","article-title":"Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods","author":"Goerdt","year":"2001","journal-title":"Proceedings STACS"},{"key":"10.1016\/S1571-0653(04)00461-5_NEWBIB11","article-title":"Problems and Theorems in Linear Algebra","volume":"Vol. 134","author":"Prasolov","year":"1994"}],"container-title":["Electronic Notes in Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304004615?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304004615?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T12:50:42Z","timestamp":1585918242000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571065304004615"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,10]]},"references-count":11,"alternative-id":["S1571065304004615"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0653(04)00461-5","relation":{},"ISSN":["1571-0653"],"issn-type":[{"value":"1571-0653","type":"print"}],"subject":[],"published":{"date-parts":[[2003,10]]}}}