{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:58:54Z","timestamp":1725559134408},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241317"},{"type":"electronic","value":"9783540305514"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_42","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:15:37Z","timestamp":1279044937000},"page":"470-483","source":"Crossref","is-referenced-by-count":2,"title":["On the Hardness and Easiness of Random 4-SAT Formulas"],"prefix":"10.1007","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":"297","reference":[{"key":"42_CR1","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/BF01277956","volume":"5","author":"N. Alon","year":"1995","unstructured":"Alon, N., Feige, U., Widgerson, A., Zuckerman, D.: Derandomized Graph Products. Computational Complexity\u00a05, 60\u201375 (1995)","journal-title":"Computational Complexity"},{"doi-asserted-by":"crossref","unstructured":"Alon, N., Kahale, N.: A spectral technique for coloring random 3-colourable graphs. DIMACS TR 94-35 (1994)","key":"42_CR2","DOI":"10.1145\/195058.195187"},{"key":"42_CR3","series-title":"LNCS","first-page":"345","volume-title":"Proc. 5th IPCO 1996","author":"H. Chen","year":"1996","unstructured":"Chen, H., Frieze, A.: Coloring bipartite hypergraphs. In: Proc. 5th IPCO 1996. LNCS, pp. 345\u2013358. Springer, Heidelberg (1996)"},{"doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Goerdt, A., Lanka, A.: Strong Refutation Heuristics for Random k-SAT. RANDOM, To appear (2004), http:\/\/www.tu-chemnitz.de\/informatik\/HomePages\/TI\/publikationen.php","key":"42_CR4","DOI":"10.1007\/978-3-540-27821-4_28"},{"unstructured":"Coja-Oghlan, A., Goerdt, A., Lanka, A., Sch\u00e4dlich, F.: Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2k-SAT. Theoretical Computer Science. (To appear)","key":"42_CR5"},{"doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proc. 24th STOC, pp. 534\u2013543 (2002)","key":"42_CR6","DOI":"10.1145\/509907.509985"},{"unstructured":"Feige, U., Ofek, E.: Easily refutable subformulas of large random 3CNF formulas, http:\/\/www.wisdom.weizmann.ac.il\/~erano\/","key":"42_CR7"},{"key":"42_CR8","volume-title":"Proc. SoDA 2002","author":"A. Flaxman","year":"2002","unstructured":"Flaxman, A.: A spectral technique for random satisfiable 3CNF formulas. In: Proc. SoDA 2002, SIAM, Philadelphia (2002)"},{"unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability (1979)","key":"42_CR9"},{"key":"42_CR10","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1017\/S0963548303005637","volume":"12","author":"A. Goerdt","year":"2003","unstructured":"Goerdt, A., Jurdzinski, T.: Some results on random unsatisfiable k-SAT instances and approximation algorithms applied to random structures. Combinatorics, Probability and Computing\u00a012, 245\u2013267 (2003)","journal-title":"Combinatorics, Probability and Computing"},{"doi-asserted-by":"crossref","unstructured":"Goerdt, A., Lanka, A.: Recognizing more random unsatisfiable 3-SAT instances efficiently. Proc. Typical Case Complexity and Phase Transitions, Satellite Workshop of Logic in Computer Science (Ottawa). To appear (2003)","key":"42_CR11","DOI":"10.1016\/S1571-0653(04)00461-5"},{"unstructured":"Goerdt, A., Lanka, A.: The algorithmic hardness and easiness of random 4-SAT formulas. Technical report, http:\/\/www.tu-chemnitz.de\/informatik\/HomePages\/TI\/publikationen.php","key":"42_CR12"},{"key":"42_CR13","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is Hard to Approximate within n 1\u2009\u2212\u2009\u03b5 . Acta Mathematica\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"key":"42_CR14","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random graphs. John Wiley and Sons, Chichester (2000)"},{"issue":"3","key":"42_CR15","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotsky","year":"1988","unstructured":"Lubotsky, A., Phillips, R., Sarnak, P.: Ramanujan Graphs. Combinatorica\u00a08(3), 261\u2013277 (1988)","journal-title":"Combinatorica"},{"unstructured":"Peeters, R.: The maximum edge biclique problem is ${\\mathcal NP}$ -complete. Research Memorandum 789, Faculty of Economics and Business Administration, Tilberg University (2000), http:\/\/econpapers.hhs.se\/paper\/dgrkubrem\/2000789.htm","key":"42_CR16"},{"unstructured":"Strang, G.: Linear Algebra and its Applications. Harcourt Brace Jovanovich (1988)","key":"42_CR17"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30551-4_42.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:21:27Z","timestamp":1605759687000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}