Commutativity in the algorithmic Lovász local lemma

V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056.


Journal Article | Published | English
Department
Abstract
We consider the recent formulation of the algorithmic Lov ́asz Local Lemma [N. Har-vey and J. Vondr ́ak, inProceedings of FOCS, 2015, pp. 1327–1345; D. Achlioptas and F. Iliopoulos,inProceedings of SODA, 2016, pp. 2024–2038; D. Achlioptas, F. Iliopoulos, and V. Kolmogorov,ALocal Lemma for Focused Stochastic Algorithms, arXiv preprint, 2018] for finding objects that avoid“bad features,” or “flaws.” It extends the Moser–Tardos resampling algorithm [R. A. Moser andG. Tardos,J. ACM, 57 (2010), 11] to more general discrete spaces. At each step the method picks aflaw present in the current state and goes to a new state according to some prespecified probabilitydistribution (which depends on the current state and the selected flaw). However, the recent formu-lation is less flexible than the Moser–Tardos method since it requires a specific flaw selection rule,whereas the algorithm of Moser and Tardos allows an arbitrary rule (and thus can potentially beimplemented more efficiently). We formulate a new “commutativity” condition and prove that it issufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additionalassumption. We then show that existing resampling oracles for perfect matchings and permutationsdo satisfy this condition.
Publishing Year
Date Published
2018-11-08
Journal Title
SIAM Journal on Computing
Volume
47
Issue
6
Page
2029-2056
IST-REx-ID

Cite this

Kolmogorov V. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 2018;47(6):2029-2056. doi:10.1137/16m1093306
Kolmogorov, V. (2018). Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing, 47(6), 2029–2056. https://doi.org/10.1137/16m1093306
Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” SIAM Journal on Computing 47, no. 6 (2018): 2029–56. https://doi.org/10.1137/16m1093306.
V. Kolmogorov, “Commutativity in the algorithmic Lovász local lemma,” SIAM Journal on Computing, vol. 47, no. 6, pp. 2029–2056, 2018.
Kolmogorov V. 2018. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 47(6), 2029–2056.
Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” SIAM Journal on Computing, vol. 47, no. 6, Society for Industrial & Applied Mathematics (SIAM), 2018, pp. 2029–56, doi:10.1137/16m1093306.

Link(s) to Main File(s)
Access Level
OA Open Access
Material in IST:
Earlier Version

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1506.08547

Search this title in

Google Scholar