Document Open Access Logo

A New Notion of Commutativity for the Algorithmic Lovász Local Lemma

Authors David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.31.pdf
  • Filesize: 0.76 MB
  • 25 pages

Document Identifiers

Author Details

David G. Harris
  • University of Maryland, College Park, MD, USA
Fotis Iliopoulos
  • Institute for Advanced Study, Princeton, NJ, USA
Vladimir Kolmogorov
  • Institute of Science and Technology, Klosterneuburg, Austria

Funding

  • Iliopoulos, Fotis: This material is based upon work directly supported by the IAS Fund for Math and indirectly supported by the National Science Foundation Grant No. CCF-1900460. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. This work is also supported by the National Science Foundation Grant No. CCF-1815328.
  • Kolmogorov, Vladimir: Supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160.

Cite AsGet BibTex

David G. Harris, Fotis Iliopoulos, and Vladimir Kolmogorov. A New Notion of Commutativity for the Algorithmic Lovász Local Lemma. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 31:1-31:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.31

Abstract

The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthrough paper of Moser & Tardos and follow-up works revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. In particular, it can be seen as a sufficient condition for this type of algorithms to converge fast. Besides conditions for convergence, many other natural questions can be asked about algorithms; for instance, "are they parallelizable?", "how many solutions can they output?", "what is the expected "weight" of a solution?". These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probabilistic algorithms
  • Mathematics of computing → Combinatorics
Keywords
  • Lovász Local Lemma
  • Resampling
  • Moser-Tardos algorithm
  • latin transversal
  • commutativity

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. Random walks that find perfect objects and the Lovász local lemma. Journal of the ACM, 63(3):Article #22, 2016. URL: https://doi.org/10.1145/2818352.
  2. Dimitris Achlioptas, Fotis Iliopoulos, and Vladimir Kolmogorov. A local lemma for focused stochastic algorithms. SIAM Journal on Computing, 48(5):1583-1602, 2019. URL: https://doi.org/10.1137/16M109332X.
  3. Dimitris Achlioptas, Fotis Iliopoulos, and Alistair Sinclair. Beyond the Lovász local lemma: Point to set correlations and their algorithmic applications. In Proc. 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 725-744, 2019. Google Scholar
  4. Noga Alon, Joel Spencer, and Prasad Tetali. Covering with latin transversals. Discrete applied mathematics, 57(1):1-10, 1995. Google Scholar
  5. 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: https://doi.org/10.1017/S0963548311000253.
  6. Karthekeyan Chandrasekaran, Navin Goyal, and Bernhard Haeupler. Deterministic algorithms for the Lovász local lemma. SIAM Journal on Computing, 42(6):2132-2155, 2013. URL: https://doi.org/10.1137/100799642.
  7. Antares Chen, David G. Harris, and Aravind Srinivasan. Partial resampling to approximate covering integer programs. Random Structures & Algorithms, pages 69-93, 2021. Google Scholar
  8. Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed algorithms for the Lovász local lemma and graph coloring. Distributed Computing, 30(4):261-280, 2017. Google Scholar
  9. 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. Erdos on his 60th birthday), Vol. II, pages 609-627. Colloq. Math. Soc. János Bolyai, Vol. 10. 1975. Google Scholar
  10. Paul Erdös and Joel Spencer. Lopsided Lovász local lemma and latin transversals. Discrete Applied Mathematics, 30(2-3):151-154, 1991. URL: https://doi.org/10.1016/0166-218X(91)90040-4.
  11. Bernhard Haeupler and David G. Harris. Parallel algorithms and concentration bounds for the Lovász local lemma via witness DAGs. ACM Transactions on Algorithms, 13(4):Article #25, 2017. Google Scholar
  12. Bernhard Haeupler, Barna Saha, and Aravind Srinivasan. New constructive aspects of the Lovász local lemma. Journal of the ACM, 58(6):Article #28, 2011. URL: https://doi.org/10.1145/2049697.2049702.
  13. David G. Harris. Lopsidependency in the Moser-Tardos framework: Beyond the lopsided Lovász local lemma. ACM Transactions on Algorithms, 13(1):Article #17, 2016. URL: https://doi.org/10.1145/3015762.
  14. David G. Harris. New bounds for the Moser-Tardos distribution. Random Structures & Algorithms, 57(1):97-131, 2020. Google Scholar
  15. David G. Harris. Oblivious resampling oracles and parallel algorithms for the Lopsided Lovász Local Lemma. ACM Transactions on Algorithms, 17(1):Article #1, 2021. Google Scholar
  16. David G. Harris and Aravind Srinivasan. Algorithmic and enumerative aspects of the Moser-Tardos distribution. ACM Transactions on Algorithms, 13(3):Article #33, 2017. Google Scholar
  17. David G. Harris and Aravind Srinivasan. A constructive Lovász Local Lemma for permutations. Theory of Computing, 13(1):Article #17, 2017. Google Scholar
  18. David G. Harris and Aravind Srinivasan. The Moser-Tardos framework with partial resampling. Journal of the ACM, 66(5):Article #36, 2019. Google Scholar
  19. Nicholas J. A. Harvey and Jan Vondrák. An algorithmic proof of the Lovász local lemma via resampling oracles. SIAM Journal on Computing, 49(2):394-428, 2020. Google Scholar
  20. Fotis Iliopoulos. Commutative algorithms approximate the LLL-distribution. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2018. Google Scholar
  21. Fotis Iliopoulos and Alistair Sinclair. Efficiently list-edge coloring multigraphs asymptotically optimally. In Proc. 14th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2319-2336, 2020. Google Scholar
  22. Kashyap Kolipaka and Mario Szegedy. Moser and Tardos meet Lovász. In Proc. 43rd annual ACM Symposium on Theory of Computing (STOC), pages 235-244, 2011. Google Scholar
  23. Vladimir Kolmogorov. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing, 47(6):2029-2056, 2018. Google Scholar
  24. László Lovász. Submodular functions and convexity. In Mathematical Programming: the State of the Art, pages 235-257. Springer, 1983. Google Scholar
  25. Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász local lemma. Journal of the ACM, 57(2):Article #11, 2010. URL: https://doi.org/10.1145/1667053.1667060.
  26. Wesley Pegden. An extension of the Moser-Tardos algorithmic local lemma. SIAM Journal on Discrete Mathematics, 28(2):911-917, 2014. URL: https://doi.org/10.1137/110828290.
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