Journal
JOURNAL OF THE ACM
Volume 63, Issue 3, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2818352
Keywords
Lovasz Local Lemma; LLL; entropic method
Categories
Funding
- ERC Starting Grant [210743]
- Alfred P. Sloan Research Fellowship
- NSF grants [CCF-1514128, CCF-1514434]
- European Research Council (ERC) [210743] Funding Source: European Research Council (ERC)
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1514128, 1514434] Funding Source: National Science Foundation
Ask authors/readers for more resources
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 the inevitability of reaching a sink is established by bounding the entropy of the walk as a function of time.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available