In probability theory, if a large number of events are all independent of one another and each has probability less than 1, then there is a positive (possibly small) probability that none of the events will occur.
The Lovasz local lemma allows to relax the independence condition slightly:
As long as the events are “mostly” independent from one another and aren’t individually too likely, then there will still be a positive probability that none of them occurs.
It is commonly used in the probabilistic method for existence proofs.
For an overview check out:
wikipedia page on Lovasz local lemma
wikipedia page on Algorithmic LLL
Tao Blog on Moser’s entropy compression argument
Complexity blog on Kolmogorov Complexity Proof of the LLL
(2009) A constructive proof of the general Lovasz Local Lemma
(2015) An alternative proof for the constructive Asymmetric LLL
(2016) A Simple Algorithmic Proof of the Symmetric Lopsided LLL
(2023) Deterministic algorithms for the LLL: Simpler, general and parallel
(2010) Everywhere complex sequences and probabilistic method
(2013) Probabilistic Constructions and Computable Version of LLL
(2023) Constructive Applications of the left-handed LLL (PhD thesis)
(2010) Kolmogorov complexity, Lovasz local lemma and critical exponents
(2011) A Kolmogorov Complexity Proof of the LLL for Satisfiability
(1984) There exists an infinite 01-sequence containing no near identical intervals
(2005) Insufficiency of four known necessary conditions on string unavoidability
(2010) Highly non-repetitive sequences: winning strategies from LLL
(2023) Formal Probabilistic Methods for Combinatorial Structures using LLL