期刊
JOURNAL OF THE ACM
卷 63, 期 3, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2818352
关键词
Lovasz Local Lemma; LLL; entropic method
类别
资金
- 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
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据