Document Open Access Logo

Commutative Algorithms Approximate the LLL-distribution

Author Fotis Iliopoulos

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.44.pdf
  • Filesize: 0.52 MB
  • 20 pages

Document Identifiers

Author Details

Fotis Iliopoulos
  • University of California Berkeley, USA

Funding

  • Iliopoulos, Fotis: Research supported by NSF grant CCF-1514434 and the Onassis Foundation

Cite AsGet BibTex

Fotis Iliopoulos. Commutative Algorithms Approximate the LLL-distribution. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 44:1-44:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.44

Abstract

Following the groundbreaking Moser-Tardos algorithm for the Lovász Local Lemma (LLL), a series of works have exploited a key ingredient of the original analysis, the witness tree lemma, in order to: derive deterministic, parallel and distributed algorithms for the LLL, to estimate the entropy of the output distribution, to partially avoid bad events, to deal with super-polynomially many bad events, and even to devise new algorithmic frameworks. Meanwhile, a parallel line of work has established tools for analyzing stochastic local search algorithms motivated by the LLL that do not fall within the Moser-Tardos framework. Unfortunately, the aforementioned results do not transfer to these more general settings. Mainly, this is because the witness tree lemma, provably, does not longer hold. Here we prove that for commutative algorithms, a class recently introduced by Kolmogorov and which captures the vast majority of LLL applications, the witness tree lemma does hold. Armed with this fact, we extend the main result of Haeupler, Saha, and Srinivasan to commutative algorithms, establishing that the output of such algorithms well-approximates the LLL-distribution, i.e., the distribution obtained by conditioning on all bad events being avoided, and give several new applications. For example, we show that the recent algorithm of Molloy for list coloring number of sparse, triangle-free graphs can output exponential many list colorings of the input graph.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Lovasz Local Lemma
  • Local Search
  • Commutativity
  • LLL-distribution
  • Coloring Triangle-free Graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dimitris Achlioptas and Fotis Iliopoulos. Focused stochastic local search and the Lovász local lemma. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 2024-2038, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch141.
  2. Dimitris Achlioptas and Fotis Iliopoulos. Random walks that find perfect objects and the Lovász local lemma. J. ACM, 63(3):22:1-22:29, 2016. URL: http://dx.doi.org/10.1145/2818352.
  3. Dimitris Achlioptas, Fotis Iliopoulos, and Alistair Sinclair. A new perspective on stochastic local search and the lovasz local lemma. CoRR, abs/1805.02026, 2018. URL: http://arxiv.org/abs/1805.02026.
  4. Noga Alon. A parallel algorithmic version of the local lemma. Random Struct. Algorithms, 2(4):367-378, 1991. URL: http://dx.doi.org/10.1002/rsa.3240020403.
  5. József Beck. An algorithmic approach to the Lovász local lemma. I. Random Structures Algorithms, 2(4):343-365, 1991. URL: http://dx.doi.org/10.1002/rsa.3240020402.
  6. Anton Bernshteyn. The johansson-molloy theorem for dp-coloring. arXiv preprint arXiv:1708.03843, 2017. Google Scholar
  7. Rodrigo Bissacot, Roberto Fernández, Aldo Procacci, and Benedetto Scoppola. An improvement of the Lovász local lemma via cluster expansion. Combinatorics, Probability & Computing, 20(5):709-719, 2011. URL: http://dx.doi.org/10.1017/S0963548311000253.
  8. Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler. Deterministic algorithms for the Lovász local lemma. SIAM J. Comput., 42(6):2132-2155, 2013. URL: http://dx.doi.org/10.1137/100799642.
  9. Antares Chen, David G. Harris, and Aravind Srinivasan. Partial resampling to approximate covering integer programs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1984-2003. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch139.
  10. Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput., 17(2):230-261, 1988. URL: http://dx.doi.org/10.1137/0217015.
  11. Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed algorithms for the Lovász local lemma and graph coloring. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC '14, Paris, France, July 15-18, 2014, pages 134-143. ACM, 2014. URL: http://dx.doi.org/10.1145/2611462.2611465.
  12. Artur Czumaj and Christian Scheideler. Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovász local lemma. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), pages 30-39, 2000. Google Scholar
  13. Paul Erdős and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, pages 609-627. Colloq. Math. Soc. János Bolyai, Vol. 10. North-Holland, Amsterdam, 1975. Google Scholar
  14. Bernhard Haeupler and David G Harris. Parallel algorithms and concentration bounds for the Lovász local lemma via witness-DAGs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1170-1187. SIAM, 2017. Google Scholar
  15. Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. New constructive aspects of the Lovász local lemma. J. ACM, 58(6):Art. 28, 28, 2011. URL: http://dx.doi.org/10.1145/2049697.2049702.
  16. David G. Harris. New bounds for the Moser-Tardos distribution: Beyond the Lovasz local lemma. CoRR, abs/1610.09653, 2016. URL: http://arxiv.org/abs/1610.09653.
  17. David G. Harris. Oblivious resampling oracles and parallel algorithms for the lopsided Lovász local lemma. CoRR, abs/1702.02547, 2017. URL: http://arxiv.org/abs/1702.02547.
  18. David G. Harris and Aravind Srinivasan. The Moser-Tardos framework with partial resampling. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 469-478. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.57.
  19. David G. Harris and Aravind Srinivasan. A constructive algorithm for the Lovász local lemma on permutations. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 907-925. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.68.
  20. David G. Harris and Aravind Srinivasan. Algorithmic and enumerative aspects of the Moser-Tardos distribution. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 2004-2023, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch140.
  21. Nicholas J. A. Harvey and Jan Vondrák. An algorithmic proof of the Lovász local lemma via resampling oracles. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1327-1346. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.85.
  22. Kashyap Babu Rao Kolipaka and Mario Szegedy. Moser and Tardos meet Lovász. In STOC, pages 235-244. ACM, 2011. URL: http://dx.doi.org/10.1145/1993636.1993669.
  23. Kashyap Babu Rao Kolipaka, Mario Szegedy, and Yixin Xu. A sharper local lemma with improved applications. In Anupam Gupta, Klaus Jansen, José D. P. Rolim, and Rocco A. Servedio, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, volume 7408 of Lecture Notes in Computer Science, pages 603-614. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32512-0_51.
  24. Vladimir Kolmogorov. Commutativity in the algorithmic Lovász local lemma. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 780-787. IEEE Computer Society, 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.88.
  25. Linyuan Lu and Laszlo A Szekely. A new asymptotic enumeration technique: the Lovász local lemma. arXiv preprint arXiv:0905.3983, 2009. Google Scholar
  26. Michael Molloy. The list chromatic number of graphs with small clique number. arXiv preprint arXiv:1701.09133, 2017. Google Scholar
  27. Michael Molloy and Bruce Reed. Further algorithmic aspects of the local lemma. In STOC '98 (Dallas, TX), pages 524-529. ACM, New York, 1999. Google Scholar
  28. Robin A. Moser. A constructive proof of the Lovász local lemma. In STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing, pages 343-350. ACM, New York, 2009. Google Scholar
  29. Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász local lemma. J. ACM, 57(2):Art. 11, 15, 2010. URL: http://dx.doi.org/10.1145/1667053.1667060.
  30. Christos H. Papadimitriou. On selecting a satisfying truth assignment. In FOCS, pages 163-169. IEEE Computer Society, 1991. URL: http://dx.doi.org/10.1109/SFCS.1991.185365.
  31. Wesley Pegden. An extension of the Moser-Tardos algorithmic local lemma. SIAM J. Discrete Math., 28(2):911-917, 2014. URL: http://dx.doi.org/10.1137/110828290.
  32. J.B. Shearer. On a problem of Spencer. Combinatorica, 5(3):241-245, 1985. URL: http://dx.doi.org/10.1007/BF02579368.
  33. Aravind Srinivasan. Improved algorithmic versions of the Lovász local lemma. In Shang-Hua Teng, editor, SODA, pages 611-620. SIAM, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347150.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact