{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:58:18Z","timestamp":1787507898214,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_45","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"519-530","source":"Crossref","is-referenced-by-count":12,"title":["Easily Refutable Subformulas of Large Random 3CNF Formulas"],"prefix":"10.1007","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eran","family":"Ofek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"2","key":"45_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"E. Ben-Sasson","year":"2001","unstructured":"Ben-Sasson, E., Wigderson, A.: Short proofs are narrow-resolution made simple. Journal of the ACM (JACM)\u00a048(2), 149\u2013169 (2001)","journal-title":"Journal of the ACM (JACM)"},{"issue":"4","key":"45_CR2","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chvatal","year":"1988","unstructured":"Chvatal, V., Szemeredi, E.: Many hard examples for resolution. Journal of the ACM\u00a035(4), 759\u2013768 (1988)","journal-title":"Journal of the ACM"},{"key":"45_CR3","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Goerdt, A., Lanka, A., Schadlich, F.: Certifying unsatisfiability of random 2k-sat formulas using approximation techniques. In: Proc. of the 14th International Symposium on Fundamentals of Computation Theory (2003)","DOI":"10.1007\/978-3-540-45077-1_3"},{"key":"45_CR4","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proc. of the 34th Annual ACM Symposium on Theory of Computing, pp. 534\u2013543 (2002)","DOI":"10.1145\/509907.509985"},{"key":"45_CR5","unstructured":"Feige, U., Ofek, E.: Spectral techniques applied to sparse random graphs. Technical report, Weizmann Institute of Science (2003)"},{"issue":"4","key":"45_CR6","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1090\/S0894-0347-99-00305-7","volume":"12","author":"E. Friedgut","year":"1999","unstructured":"Friedgut, E., Bourgain, J.: Sharp thresholds of graph properties, and the k-sat problem. JAMS: Journal of the American Mathematical Society\u00a012(4), 1017\u20131054 (1999)","journal-title":"JAMS: Journal of the American Mathematical Society"},{"key":"45_CR7","doi-asserted-by":"crossref","unstructured":"Friedman, J., Goerdt, A., Krivelevich, M.: Recognizing more unsatisfiable random 3-sat instances efficiently. Technical report (2003)","DOI":"10.1016\/S1571-0653(04)00461-5"},{"key":"45_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/3-540-44693-1_26","volume-title":"STACS 2001","author":"A. Goerdt","year":"2001","unstructured":"Goerdt, A., Krivelevich, M.: Efficient recognition of random unsatisfiable k-SAT instances by spectral methods. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 294\u2013304. Springer, Heidelberg (2001)"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Goerdt, A., Lanka, A.: Recognizing more random 3-sat instances efficiently (2003) (manuscript)","DOI":"10.1016\/S1571-0653(04)00461-5"},{"key":"45_CR10","unstructured":"Hajiaghayi, M., Sorkin, G.B.: The satisfiability threshold for random 3-SAT is at least 3.52 (2003), http:\/\/arxiv.org\/abs\/math.CO\/0310193"},{"issue":"2","key":"45_CR11","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1002\/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P","volume":"17","author":"S. Janson","year":"2000","unstructured":"Janson, S., Stamatiou, Y.C., Vamvakari, M.: Bounding the unsatisfiability threshold of random 3-sat. Random Structures and Algorithms\u00a017(2), 103\u2013116 (2000)","journal-title":"Random Structures and Algorithms"},{"key":"45_CR12","doi-asserted-by":"crossref","unstructured":"Kaporis, A.C., Kirousis, L.M., Lalas, E.G.: Selecting complementary pairs of literals. In: Proc. LICS 2003 Workshop on Typical Case Complexity and Phase Transitions (June 2003)","DOI":"10.1016\/S1571-0653(04)00462-7"},{"key":"45_CR13","doi-asserted-by":"crossref","unstructured":"Zwick, U.: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In: Proc. of the 31st Annual ACM Symposium on Theory of Computing, pp. 679\u2013687 (1999)","DOI":"10.1145\/301250.301431"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:23:57Z","timestamp":1605741837000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}