Name
Abstract | ||
|---|---|---|
We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's entropic method proof of the Lovasz Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser's argument, the key point is that algorithmic progress is measured in terms of entropy rather than energy (number of violated constraints) so that termination can be established even under the proliferation of states in which every step of the algorithm (random walk) increases the total number of violated constraints. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/FOCS.2014.59 | Foundations of Computer Science |
Keywords | Field | DocType |
computability,directed graphs,entropy,random processes,theorem proving,LLL,Lovέsz Local Lemma,Moser's entropic method proof,algorithmic local lemma,algorithmic progress,directed graph,entropy,satisfiability,uniform random walk,Entropic Method,Lovasz Local Lemma,Random Walks | Discrete mathematics,Combinatorics,Algorithmic Lovász local lemma,Random walk,Satisfiability,Directed graph,Probabilistic method,Lovász local lemma,State space,Lemma (mathematics),Mathematics | Conference |
Volume | Issue | ISSN |
63 | 3 | 0272-5428 |
Citations | PageRank | References |
8 | 0.48 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dimitris Achlioptas | 1 | 2037 | 174.89 |
| Fotis Iliopoulos | 2 | 13 | 5.28 |