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.
Attributes | Values |
---|
rdfs:label
| - Algorithmic Lovász local lemma (en)
|
rdfs:comment
| - 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. (en)
|
sameAs
| |
dbp:wikiPageUsesTemplate
| |
Subject
| |
prov:wasDerivedFrom
| |
Wikipage page ID
| |
page length (characters) of wiki page
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
has abstract
| - 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 and Gábor Tardos can compute an assignment to the random variables such that all events are avoided. (en)
|
foaf:isPrimaryTopicOf
| |
is Wikipage redirect
of | |
is Link from a Wikipage to another Wikipage
of | |
is foaf:primaryTopic
of | |