Oblivious resampling oracles and parallel algorithms for the lopsided lovász local lemma
Pages 841 - 860
Abstract
The Lovász Local Lemma (LLL) is a probabilistic tool which shows that, if a collection of "bad" events B in a probability space are not too likely and not too interdependent, then there is a positive probability that no bad-events in B occur. Moser & Tardos (2010) gave sequential and parallel algorithms which transformed most applications of the variable-assignment LLL into efficient algorithms. A framework of Harvey & Vondrák (2015) based on "resampling oracles" extended this give very general sequential algorithms for other probability spaces satisfying the Lopsided Lovász Local Lemma (LLLL).
We describe a new structural property of resampling oracles which holds for all known resampling oracles, which we call "obliviousness." Essentially, it means that the interaction between two bad-events B, B′ depends only on the randomness used to resample B, and not on the precise state within B itself.
This property has two major consequences. First, it is the key to achieving a unified parallel LLLL algorithm, which is faster than previous, problem-specific algorithms of Harris (2016) for the variable-assignment LLLL algorithm and of Harris & Srinivasan (2014) for permutations. This new algorithm extends a framework of Kolmogorov (2016), and gives the first RNC algorithms for rainbow perfect matchings and rainbow hamiltonian cycles of Kn.
Second, this property allows us to build LLLL probability spaces out of a relatively simple "atomic" set of events. It was intuitively clear that existing LLLL spaces were built in this way; but the obliviousness property formalizes this and gives a way of automatically turning a resampling oracle for atomic events into a resampling oracle for conjunctions of them. Using this framework, we get the first sequential resampling oracle for rainbow perfect matchings on the complete s-uniform hypergraph Kn(s), and the first commutative resampling oracle for hamiltonian cycles of Kn.
References
[1]
Achlioptas, D., Iliopoulos, F.: Random walks that find perfect objects and the Lovász Local Lemma. Journal of the ACM 63-3, Article #22 (2016)
[2]
Albert, M., Frieze, A., Reed, B.: Multicoloured Hamilton Cycles. The Electronic Journal of Combinatorics 2-1, R10 (1995)
[3]
Bissacot, R., Fernandez, R., Procacci, A., Scoppola, B.: An improvement of the Lovász Local Lemma via cluster expansion. Combinatorics, Probability and Computing 20-5, pp. 709--719 (2011)
[4]
Blelloch, G., Fineman, J., Shun, J.: Greedy sequential maximal independent set and matching are parallel on average. Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 308--317 (2012)
[5]
Brandt, S., Fischer, O., Hirvonen, J., Keller, B., Lempiäinen, T., Rybicki, J., Suomela, J., Uitto, J.: A lower bound for the distributed Lováasz Local Lemma. Proceedings of the 48th ACM Symposium on Theory of Computing (STOC), pp. 479--488 (2015)
[6]
Chandrasekaran, K., Goyal, N., Haeupler, B.: Deterministic algorithms for the Lovász local lemma. SIAM Journal on Computing 42-6, pp. 2132--2155 (2013)
[7]
Chung, K., Pettie, S., Su, H.: Distributed algorithms for the Lovász local lemma and graph coloring. Proceedings of the 2014 ACM Symposium on Principles of Distributed Computation (PODC), pp. 134--143 (2014)
[8]
Cook, S.: A taxonomy of problems with fast parallel algorithms. Information and Control 64, pp. 2--22 (1985)
[9]
Erdős, P., Lovász, L.: Problems and results on 3-chromatic hypergraphs and some related questions. In A. Hajnal, R. Rado, and V. T. Sos, eds. Infinite and Finite Sets II, pp. 607--726 (1975)
[10]
Erdős, P., Spencer, J.: Lopsided Lovász Local Lemma and Latin transversals. Discrete Applied Math 30, pp. 151--154 (1990)
[11]
Fischer, M., Ghaffari, M.: Sublogarithmic distributed algorithms for Lovász Local lemma, and the complexity hierarchy. Proceedings of the 31st International Symposium on Distributed Computing (DISC), p. 18 (2017)
[12]
Fischer, M., Noever, A.: Tight analysis of randomized greedy MIS. Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2152 -- 2160 (2018)
[13]
Gebauer, H., Szabó, T., Tardos, G.: The local lemma is asymptotically tight for SAT. Journal of the ACM 63-5, Article #43 (2016)
[14]
Ghaffari, M.: An improved distributed algorithm for maximal independent set. Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 270--2777 (2016)
[15]
Ghaffari, M., Harris, D., Kuhn, F.: On derandomizing local distributed algorithms. To appears in FOCS 2018.
[16]
Haeupler, B., Harris, D.: Parallel algorithms and concentration bounds for the Lovász Local Lemma via witness DAGs. ACM Transactions on Algorithms 13-4, Article #53 (2017)
[17]
Haeupler, B., Saha, B., Srinivasan, A.: New constructive aspects of the Lovász Local Lemma. Journal of the ACM, 58-6 (2011)
[18]
Harris, D.: Lopsidependency in the Moser-Tardos framework: beyond the Lopsided Lovász Local Lemma. ACM Transactions on Algorithms 13-1, Article #17 (2016)
[19]
Harris, D.: New bounds for the Moser-Tardos distribution. arXiv preprint arXiv:1610.09653 (2016)
[20]
Harris, D., Srinivasan, A.: Algorithmic and enumerative aspects of the Moser-Tardos distribution. ACM Transactions on Algorithms 13-3, Article #33 (2017)
[21]
Harris, D., Srinivasan, A.: A constructive Lovász Local Lemma for permutations. Theory of Computing 13--17, pp. 1--41 (2017)
[22]
Harvey, N., Liaw, C.: Rainbow Hamilton cycles and lopsidependency. Discrete Mathematics 340, pp. 1261--1270 (2017)
[23]
Harvey, N., Vondrák, J.: An algorithmic proof of the Lopsided Lovász Local Lemma via resampling oracles. Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1327--1346 (2015)
[24]
Haxell, P.: An improved bound for the strong chromatic number. Journal of Graph Theory 58-2, pp. 148--158 (2008)
[25]
Iliopoulos, F.: Commutative algorithms approximate the LLL distribution. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pp. 44:1--44:20 (2018)
[26]
Kolipaka, K., Szegedy, M.: Moser and Tardos meet Lovász. Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 235--244 (2011)
[27]
Kolmogorov, V.: Commutativity in the algorithmic Lovász Local Lemma. Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 780--787 (2016)
[28]
Lu, L., Mohr, A., Székely, L.: Quest for negative dependency graphs. Recent Advances in Harmonic Analysis and Applications, pp. 243--256 (2012)
[29]
Lu, L., Székély, L.: Using Lovász Local Lemma in the space of random injections. The Electronic Journal of Combinatorics 13-R63 (2007)
[30]
Lu, L., Székély, L.: A new asymptotic enumeration technique: the Lovász local lemma. arXiv:0905.3983v3 (2011)
[31]
Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing 15-4, pp. 1036--1053 (1996)
[32]
McDiarmid, C.: Hypergraph coloring and the Lovász Local Lemma. Journal of Discrete Mathematics 167/168, pp. 481--486 (1995)
[33]
Moser, R., Tardos, G.: A constructive proof of the general Lovász Local Lemma. Journal of the ACM 57-2, pp. 11:1--11:15 (2010)
[34]
Pegden, W.: An extension of the Moser-Tardos algorithmic Local Lemma. SIAM Journal on Discrete Math 28-2, pp. 911--917 (2014)
[35]
Shearer, J. B.: On a problem of Spencer. Combinatorica 5, pp. 241--245 (1985)
- Oblivious resampling oracles and parallel algorithms for the lopsided lovász local lemma
Recommendations
Oblivious Resampling Oracles and Parallel Algorithms for the Lopsided Lovász Local Lemma
The Lovász Local Lemma (LLL) shows that, for a collection of “bad” events B in a probability space that are not too likely and not too interdependent, there is a positive probability that no events in B occur. Moser and Tardos (2010) gave sequential and ...
Deterministic algorithms for the Lovász Local Lemma
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithmsThe Lovász Local Lemma [5] (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on ...
Deterministic parallel algorithms for fooling polylogarithmic juntas and the lovász local lemma
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete AlgorithmsMany randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low (almost-) independence. A series of papers, beginning with work by Luby (1988) and continuing with Berger & ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- SIAM Activity Group on Discrete Mathematics
In-Cooperation
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 06 January 2019
Check for updates
Qualifiers
- Research-article
Conference
SODA '19
Sponsor:
Acceptance Rates
Overall Acceptance Rate 411 of 1,322 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 43Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)2
Reflects downloads up to 20 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in