Metraipolis › archive › dc_49bf8b71652d
Algorithmic Lovász local lemma — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-15T14:24:00.760Z
- SHA-256 of the archived text
a85eef5423f84b9c03439ff552656414f228eba46c8d3086888fba0f1a68f7b0- Stable URL of this page
https://metraipolis.com/documento/dc_49bf8b71652d
How to cite
Algorithmic Lovász local lemma — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_49bf8b71652d (Metraipolis archive dc_49bf8b71652d, sha256 a85eef5423f84b9c03439ff552656414f228eba46c8d3086888fba0f1a68f7b0)
BibTeX
@misc{dc49bf8b71652d,
title = {Algorithmic Lovász local lemma — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_49bf8b71652d; sha256 a85eef5423f84b9c03439ff552656414f228eba46c8d3086888fba0f1a68f7b0},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In theoretical computer science, the algorithmic Lovász local lemma gives an algorithmic way of constructing objects that obey a system of constraints with limited dependence. Given a finite set of bad events {A1, ..., An} in a probability space with limited dependence amongst the Ais and with specific bounds on their respective probabilities, the Lovász local lemma proves that with non-zero probability all of these events can be avoided. However, the lemma is non-constructive in that it does not provide any insight on how to avoid the bad events. If the events {A1, ..., An} are determined by a finite collection of mutually independent random variables, a simple Las Vegas algorithm with expected polynomial runtime proposed by Robin Moser and Gábor Tardos can compute an assignment to the random variables such that all events are avoided.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Combinatorics»).
Fonte: Wikipedia in inglese, voce «Algorithmic Lovász local lemma» — https://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma
Wikidata Q4724359 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q4724359
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1310006739, consultata il 2026-10-15T13:53:36.016Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: a325805b51c9e56965c4580bf6b293d820ea8ebb58cf87406522f7db86bd6694