{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T06:17:31Z","timestamp":1769235451241,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642034558","type":"print"},{"value":"9783642034565","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03456-5_3","type":"book-chapter","created":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T02:39:16Z","timestamp":1251772756000},"page":"30-54","source":"Crossref","is-referenced-by-count":11,"title":["The Lov\u00e1sz Local Lemma and Satisfiability"],"prefix":"10.1007","author":[{"given":"Heidi","family":"Gebauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robin A.","family":"Moser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"Scheder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emo","family":"Welzl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 3rd edn. John Wiley & Sons Inc., Chichester (2008)","edition":"3"},{"key":"3_CR2","first-page":"609","volume-title":"Infinite and Finite Sets (to Paul Erd\u0151s on his 60th birthday)","author":"P. Erd\u0151s","year":"1975","unstructured":"Erd\u0151s, P., Lov\u00e1sz, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In: Hajnal, A., Rado, R., S\u00f3s, V.T. (eds.) Infinite and Finite Sets (to Paul Erd\u0151s on his 60th birthday), vol.\u00a0II, pp. 609\u2013627. North-Holland, Amsterdam (1975)"},{"key":"3_CR3","first-page":"5","volume":"11","author":"P. Erd\u0151s","year":"1963","unstructured":"Erd\u0151s, P.: On a combinatorial problem. Nordisk Mat. Tidskr.\u00a011, 5\u201310, 40 (1963)","journal-title":"Nordisk Mat. Tidskr."},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/BF01897152","volume":"15","author":"P. Erd\u0151s","year":"1964","unstructured":"Erd\u0151s, P.: On a combinatorial problem. II. Acta Math. Acad. Sci. Hungar.\u00a015, 445\u2013447 (1964)","journal-title":"Acta Math. Acad. Sci. Hungar."},{"issue":"3","key":"3_CR5","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/BF02579368","volume":"5","author":"J.B. Shearer","year":"1985","unstructured":"Shearer, J.B.: On a problem of Spencer. Combinatorica\u00a05(3), 241\u2013245 (1985)","journal-title":"Combinatorica"},{"issue":"4","key":"3_CR6","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J. Beck","year":"1991","unstructured":"Beck, J.: An algorithmic approach to the Lov\u00e1sz Local Lemma. I. Random Struct. Algorithms\u00a02(4), 343\u2013365 (1991)","journal-title":"I. Random Struct. Algorithms"},{"issue":"4","key":"3_CR7","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1002\/rsa.3240020403","volume":"2","author":"N. Alon","year":"1991","unstructured":"Alon, N.: A parallel algorithmic version of the local lemma. Random Struct. Algorithms\u00a02(4), 367\u2013378 (1991)","journal-title":"Random Struct. Algorithms"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Scheideler, C.: A new algorithm approach to the general Lov\u00e1sz Local Lemma with applications to scheduling and satisfiability problems. In: Proc. 32nd Ann. ACM Symp. on Theory of Computing, pp. 38\u201347 (2000)","DOI":"10.1145\/335305.335310"},{"key":"3_CR9","unstructured":"Srinivasan, A.: Improved algorithmic versions of the Lov\u00e1sz Local Lemma. In: Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 611\u2013620 (2008)"},{"key":"3_CR10","unstructured":"Moser, R.A.: Derandomizing the Lov\u00e1sz Local Lemma more effectively. CoRR abs\/0807.2120 (2008)"},{"key":"#cr-split#-3_CR11.1","doi-asserted-by":"crossref","unstructured":"Moser, R.A.: A constructive proof of the Lov??sz Local Lemma. CoRR abs\/0810.4812 (2008);","DOI":"10.1145\/1536414.1536462"},{"key":"#cr-split#-3_CR11.2","unstructured":"Proc. 41st Ann. ACM Symp. on Theory of Computing (to appear)"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general Lov\u00e1sz Local Lemma. CoRR abs\/0903.0544 (2009)","DOI":"10.1145\/1536414.1536462"},{"issue":"2-3","key":"3_CR13","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0166-218X(91)90040-4","volume":"30","author":"P. Erd\u0151s","year":"1991","unstructured":"Erd\u0151s, P., Spencer, J.: Lopsided Lov\u00e1sz Local Lemma and Latin transversals. Discrete Appl. Math.\u00a030(2-3), 151\u2013154 (1991)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"3_CR14","first-page":"13","volume":"14","author":"L. Lu","year":"2007","unstructured":"Lu, L., Sz\u00e9kely, L.: Using Lov\u00e1sz Local Lemma in the space of random injections. Electron. J. Combin.\u00a014(1), 13, Research Paper 63 (2007) (electronic)","journal-title":"Electron. J. Combin."},{"key":"3_CR15","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness and satisfiability of bounded occurrence instances of SAT. Electronic Colloquium on Computational Complexity (ECCC)\u00a010(022) (2003)"},{"issue":"1","key":"3_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"C.A. Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified NP-complete satisfiability problem. Discrete Appl. Math.\u00a08(1), 85\u201389 (1984)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"3_CR17","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1137\/0222015","volume":"22","author":"J. Kratochv\u00edl","year":"1993","unstructured":"Kratochv\u00edl, J., Savick\u00fd, P., Tuza, Z.: One more occurrence of variables makes satisfiability jump from trivial to NP-complete. SIAM J. Comput.\u00a022(1), 203\u2013210 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1-2","key":"3_CR18","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/S0304-3975(00)00036-0","volume":"238","author":"P. Savick\u00fd","year":"2000","unstructured":"Savick\u00fd, P., Sgall, J.: DNF tautologies with a limited number of occurrences of every variable. Theoret. Comput. Sci.\u00a0238(1-2), 495\u2013498 (2000)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"3_CR19","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1137\/S0895480104445745","volume":"20","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Szeider, S.: A note on unsatisfiable k-CNF formulas with few occurrences per variable. SIAM J. Discrete Math.\u00a020(2), 523\u2013528 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Gebauer, H.: Disproof of the neighborhood conjecture with implications to SAT. CoRR abs\/0904.2541 (2009)","DOI":"10.1007\/978-3-642-04128-0_68"},{"key":"3_CR21","series-title":"Encyclopedia of Mathematics and Its Applications","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511735202","volume-title":"Combinatorial Games: Tic Tac Toe Theory","author":"J. Beck","year":"2008","unstructured":"Beck, J.: Combinatorial Games: Tic Tac Toe Theory, 1st edn. Encyclopedia of Mathematics and Its Applications, vol.\u00a0114. Cambridge University Press, Cambridge (2008)","edition":"1"},{"key":"3_CR22","unstructured":"St\u0159\u00edbrn\u00e1, J.: Between Combinatorics and Formal Logic, Master\u2019s Thesis. Charles University, Prague (1994)"},{"issue":"1-3","key":"3_CR23","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.tcs.2005.02.004","volume":"337","author":"S. Hoory","year":"2005","unstructured":"Hoory, S., Szeider, S.: Computing unsatisfiable k-SAT instances with few occurences per variable. Theoret. Comput. Sci.\u00a0337(1-3), 347\u2013359 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"1-2","key":"3_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theor. Comput. Sci.\u00a0223(1-2), 1\u201372 (1999)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"3_CR25","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","volume":"43","author":"R. Aharoni","year":"1986","unstructured":"Aharoni, R., Linial, N.: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. J. Comb. Theory, Ser. A\u00a043(2), 196\u2013204 (1986)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"3-4","key":"3_CR26","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1023\/A:1018924526592","volume":"23","author":"G. Davydov","year":"1998","unstructured":"Davydov, G., Davydova, I., Kleine B\u00fcning, H.: An efficient algorithm for the minimal unsatisfiability problem for a subclass of CNF. Ann. Math. Artificial Intelligence\u00a023(3-4), 229\u2013245 (1998)","journal-title":"Ann. Math. Artificial Intelligence"},{"key":"3_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/10703163_12","volume-title":"Computer Science Logic","author":"H. Kleine B\u00fcning","year":"1999","unstructured":"Kleine B\u00fcning, H.: An upper bound for minimal resolution refutations. In: Gottlob, G., Grandjean, E., Seyr, K. (eds.) CSL 1998. LNCS, vol.\u00a01584, pp. 171\u2013178. Springer, Heidelberg (1999)"},{"issue":"1-3","key":"3_CR28","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0166-218X(00)00245-6","volume":"107","author":"H. Kleine B\u00fcning","year":"2000","unstructured":"Kleine B\u00fcning, H.: On subclasses of minimal unsatisfiable formulas. Discrete Appl. Math.\u00a0107(1-3), 83\u201398 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"3_CR29","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/S0166-218X(02)00411-0","volume":"130","author":"S. Szeider","year":"2003","unstructured":"Szeider, S.: Homomorphisms of conjunctive normal forms. Discrete Appl. Math.\u00a0130(2), 351\u2013365 (2003)","journal-title":"Discrete Appl. Math."},{"key":"3_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/11814948_22","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"S. Porschen","year":"2006","unstructured":"Porschen, S., Speckenmeyer, E., Randerath, B.: On linear CNF formulas. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 212\u2013225. Springer, Heidelberg (2006)"},{"key":"3_CR31","doi-asserted-by":"publisher","first-page":"515","DOI":"10.4153\/CMB-1965-038-1","volume":"8","author":"H. Abbott","year":"1965","unstructured":"Abbott, H.: An application of Ramsey\u2019s Theorem to a problem of Erd\u0151s and Hajnal. Canad. Math. Bull.\u00a08, 515\u2013517 (1965)","journal-title":"Canad. Math. Bull."},{"issue":"2","key":"3_CR32","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1002\/rsa.1020","volume":"19","author":"A. Kostochka","year":"2001","unstructured":"Kostochka, A., Mubayi, D., R\u00f6dl, V., Tetali, P.: On the chromatic number of set systems. Random Struct. Algorithms\u00a019(2), 87\u201398 (2001)","journal-title":"Random Struct. Algorithms"},{"key":"3_CR33","unstructured":"Scheder, D.: Unsatisfiable linear CNF formulas are large, and difficult to construct explicitely. CoRR abs\/0905.1587 (2009)"},{"issue":"5","key":"3_CR34","doi-asserted-by":"publisher","first-page":"1046","DOI":"10.1016\/j.dam.2008.03.031","volume":"157","author":"S. Porschen","year":"2009","unstructured":"Porschen, S., Speckenmeyer, E., Zhao, X.: Linear CNF formulas and satisfiability. Discrete Appl. Math.\u00a0157(5), 1046\u20131068 (2009)","journal-title":"Discrete Appl. Math."},{"key":"3_CR35","unstructured":"Scheder, D.: Unsatisfiable linear k-CNFs exist, for every k. CoRR abs\/0708.2336 (2007)"},{"issue":"2","key":"3_CR36","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\u2014resolution made simple. J. ACM\u00a048(2), 149\u2013169 (2001)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03456-5_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T15:03:07Z","timestamp":1685113387000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03456-5_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642034558","9783642034565"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03456-5_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}