On the Locality of the Lovász Local Lemma

Davies-Peck, Peter

Abstract

The Lovász Local Lemma is a versatile result in probability theory, characterizing circumstances in which a collection of n ‘bad events’, each occurring with probability at most p and dependent on a set
of underlying random variables, can be avoided. It is a central tool of the probabilistic method, since it can be used to show that combinatorial objects satisfying some desirable properties must exist. While the original proof was existential, subsequent work has shown algorithms for the Lovász Local Lemma: that is, in circumstances in which the lemma proves the existence of some object, these algorithms can constructively find such an object. One main strand of these algorithms, which began with Moser and Tardos’s well-known result (JACM 2010), involves iteratively resampling the dependent variables of satisfied bad events until none remain satisfied.
In this paper, we present a novel analysis that can be applied to resampling-style Lovász Local Lemma algorithms. This analysis shows that an output assignment for the dependent variables of most events can be determined only from O(log log 1/p n)-radius local neighborhoods, and that the events whose variables may still require resampling can be identified from these neighborhoods. This allows us to improve randomized complexities for the constructive Lovász Local Lemma (with polynomial criterion) in several parallel and distributed models. In particular, we obtain:
• A LOCAL algorithm with O(log log_1/p n) node-averaged complexity (while matching the O(log_1/p n) worst-case complexity of Chung, Pettie, and Su).
• An algorithm for the LCA and VOLUME models requiring d
O(log log_1/p n) probes per query.
• An O(log log log_1/p n)-round algorithm for CONGESTED CLIQUE, linear space MPC, and Heterogenous MPC.

Citation

Davies-Peck, P. (2025, June). On the Locality of the Lovász Local Lemma. Presented at 57th Annual ACM Symposium on Theory of Computing (STOC '25), Prague

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 57th Annual ACM Symposium on Theory of Computing (STOC '25)
• Start Date: Jun 23, 2025
• End Date: Jun 27, 2025
• Acceptance Date: Jan 31, 2025
• Deposit Date: Feb 17, 2025
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Public URL: https://durham-repository.worktribe.com/output/3488669
• Publisher URL: https://dl.acm.org/conference/stoc/proceedings