{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:04:37Z","timestamp":1740096277276,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385353"},{"type":"electronic","value":"9783642385360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_1","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T01:03:04Z","timestamp":1370221384000},"page":"1-11","source":"Crossref","is-referenced-by-count":8,"title":["The Lov\u00e1sz Local Lemma \u2013 A Survey"],"prefix":"10.1007","author":[{"given":"Mario","family":"Szegedy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Alon, N.: A parallel algorithmic version of the Local Lemma. In: FOCS, pp. 586\u2013593 (1991)","key":"1_CR1","DOI":"10.1002\/rsa.3240020403"},{"issue":"3-4","key":"1_CR2","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1002\/rsa.10057","volume":"21","author":"N. Alon","year":"2002","unstructured":"Alon, N., Grytczuk, J., Haluszczak, M., Riordan, O.: Nonrepetitive colorings of graphs. Random Struct. Algorithms\u00a021(3-4), 336\u2013346 (2002)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"1_CR3","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/rsa.3240020303","volume":"2","author":"N. Alon","year":"1991","unstructured":"Alon, N., McDiarmid, C., Reed, B.A.: Acyclic coloring of graphs. Random Struct. Algorithms\u00a02(3), 277\u2013288 (1991)","journal-title":"Random Struct. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Ambainis, A., Kempe, J., Sattath, O.: A quantum lov\u00e1sz local lemma. In: STOC, pp. 151\u2013160 (2010)","key":"1_CR4","DOI":"10.1145\/1806689.1806712"},{"issue":"4","key":"1_CR5","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\u2013366 (1991)","journal-title":"Random Struct. Algorithms"},{"unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness and satisfiability of bounded occurrence instances of sat. Electronic Colloquium on Computational Complexity (ECCC) 10(022) (2003)","key":"1_CR6"},{"issue":"5","key":"1_CR7","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1017\/S0963548311000253","volume":"20","author":"R. Bissacot","year":"2011","unstructured":"Bissacot, R., Fernandez, R., Procacci, A., Scoppola, B.: Combinatorics Probability and Computing 20(5), 709\u2013719 (2011)","journal-title":"Combinatorics Probability and Computing"},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"992","DOI":"10.1137\/1.9781611973075.80","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","author":"K. Chandrasekaran","year":"2010","unstructured":"Chandrasekaran, K., Goyal, N., Haeupler, B.: Deterministic algorithms for the lov\u00e1sz local lemma. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp. 992\u20131004. Society for Industrial and Applied Mathematics, Philadelphia (2010)"},{"unstructured":"Czumaj, A., Scheideler, C.: Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lov\u00e1sz Local Lemma. In: SODA, pp. 30\u201339 (2000)","key":"1_CR9"},{"unstructured":"Dujmovic, V., Joret, G., Wood, D.R.: Nonrepetitive colouring via entropy compression. CoRR abs\/1112.5524 (2011)","key":"1_CR10"},{"unstructured":"Erd\u00f6s, 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\u00f6s on his 60th birthday), pp. 609\u2013627 (1975)","key":"1_CR11"},{"issue":"2-3","key":"1_CR12","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0166-218X(91)90040-4","volume":"30","author":"P. Erd\u00f6s","year":"1991","unstructured":"Erd\u00f6s, P., Spencer, J.: Lopsided Lov\u00e1sz Local Lemma and latin transversals. Discrete Applied Mathematics\u00a030(2-3), 151\u2013154 (1991)","journal-title":"Discrete Applied Mathematics"},{"issue":"5","key":"1_CR13","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00493-012-2679-y","volume":"32","author":"H. Gebauer","year":"2012","unstructured":"Gebauer, H.: Disproof of the neighborhood conjecture with implications to sat. Combinatorica\u00a032(5), 573\u2013587 (2012)","journal-title":"Combinatorica"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/978-3-642-03456-5_3","volume-title":"Efficient Algorithms","author":"H. Gebauer","year":"2009","unstructured":"Gebauer, H., Moser, R.A., Scheder, D., Welzl, E.: The lov\u00e1sz local lemma and satisfiability. In: Albers, S., Alt, H., N\u00e4her, S. (eds.) Efficient Algorithms. LNCS, vol.\u00a05760, pp. 30\u201354. Springer, Heidelberg (2009)"},{"doi-asserted-by":"crossref","unstructured":"Gebauer, H., Szab\u00f3, T., Tardos, G.: The local lemma is tight for sat. In: SODA, pp. 664\u2013674 (2011)","key":"1_CR15","DOI":"10.1137\/1.9781611973082.52"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1088\/0305-4470\/20\/2\/037","volume":"20","author":"A.J. Guttmann","year":"1987","unstructured":"Guttmann, A.J.: Comment: Comment on the exact location of partition function zeros, a new method for statistical mechanics. Journal of Physics A Mathematical General\u00a020, 511\u2013512 (1987)","journal-title":"Journal of Physics A Mathematical General"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1109\/FOCS.2010.45","volume-title":"Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010","author":"B. Haeupler","year":"2010","unstructured":"Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the lov\u00e1sz local lemma. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 397\u2013406. IEEE Computer Society, Washington, DC (2010), http:\/\/dx.doi.org\/10.1109\/FOCS.2010.45"},{"issue":"2","key":"1_CR18","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."},{"doi-asserted-by":"crossref","unstructured":"Kolipaka, K.B.R., Szegedy, M.: Moser and Tardos meet Lov\u00e1sz. In: STOC, pp. 235\u2013244 (2011)","key":"1_CR19","DOI":"10.1145\/1993636.1993669"},{"key":"1_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1007\/978-3-642-32512-0_51","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"K. Kolipaka","year":"2012","unstructured":"Kolipaka, K., Szegedy, M., Xu, Y.: A sharper local lemma with improved applications. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM 2012. LNCS, vol.\u00a07408, pp. 603\u2013614. Springer, Heidelberg (2012)"},{"issue":"1","key":"1_CR21","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."},{"doi-asserted-by":"crossref","unstructured":"Molloy, M., Reed, B.A.: Further algorithmic aspects of the Local Lemma. In: STOC, pp. 524\u2013529 (1998)","key":"1_CR22","DOI":"10.1145\/276698.276866"},{"doi-asserted-by":"crossref","unstructured":"Moser, R.A.: A constructive proof of the Lov\u00e1sz Local Lemma. In: STOC, pp. 343\u2013350 (2009)","key":"1_CR23","DOI":"10.1145\/1536414.1536462"},{"doi-asserted-by":"crossref","unstructured":"Moser, R.A., Tardos, G.: A constructive proof of the general Lov\u00e1sz Local Lemma. J. ACM\u00a057(2) (2010)","key":"1_CR24","DOI":"10.1145\/1667053.1667060"},{"unstructured":"Papadimitriou, C.H.: On selecting a satisfying truth assignment (extended abstract). In: FOCS, pp. 163\u2013169 (1991)","key":"1_CR25"},{"issue":"1-2","key":"1_CR26","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1002\/rsa.20354","volume":"38","author":"W. Pegden","year":"2011","unstructured":"Pegden, W.: Highly nonrepetitive sequences: Winning strategies from the local lemma. Random Struct. Algorithms\u00a038(1-2), 140\u2013161 (2011)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"1_CR27","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1002\/rsa.20439","volume":"41","author":"W. Pegden","year":"2012","unstructured":"Pegden, W.: The lefthanded local lemma characterizes chordal dependency graphs. Random Struct. Algorithms\u00a041(4), 546\u2013556 (2012)","journal-title":"Random Struct. Algorithms"},{"issue":"1-2","key":"1_CR28","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. Theor. Comput. Sci.\u00a0238(1-2), 495\u2013498 (2000)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-sat and constraint satisfaction problems. In: FOCS, pp. 410\u2013414 (1999)","key":"1_CR29"},{"issue":"1-2","key":"1_CR30","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1017\/S0963548305007182","volume":"15","author":"A.D. Scott","year":"2006","unstructured":"Scott, A.D., Sokal, A.D.: On dependency graphs and the lattice gas. Combinatorics, Probability & Computing\u00a015(1-2), 253\u2013279 (2006)","journal-title":"Combinatorics, Probability & Computing"},{"issue":"3","key":"1_CR31","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":"0","key":"1_CR32","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0012-365X(77)90044-9","volume":"20","author":"J. Spencer","year":"1977","unstructured":"Spencer, J.: Asymptotic lower bounds for Ramsey functions. Discrete Mathematics\u00a020(0), 69\u201376 (1977)","journal-title":"Discrete Mathematics"},{"unstructured":"Srinivasan, A.: Improved algorithmic versions of the Lov\u00e1sz Local Lemma. In: SODA, pp. 611\u2013620 (2008)","key":"1_CR33"},{"key":"1_CR34","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1142\/S0129183199000401","volume":"10","author":"S. Todo","year":"1999","unstructured":"Todo, S.: Transfer-matrix study of negative-fugacity singularity of hard-core lattice gas. International Journal of Modern Physics C\u00a010, 517\u2013529 (1999)","journal-title":"International Journal of Modern Physics C"},{"doi-asserted-by":"crossref","unstructured":"Wood, D.W.: The exact location of partition function zeros, a new method for statistical mechanics. Journal of Physics A: Mathematical and General 18(15), L917 (1985)","key":"1_CR35","DOI":"10.1088\/0305-4470\/18\/15\/003"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T18:46:53Z","timestamp":1645642013000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}