logo

SCIENTIA SINICA Informationis, Volume 50 , Issue 11 : 1680(2020) https://doi.org/10.1360/SSI-2019-0287

New versions of Lovász Local Lemma and their applications

More info
  • ReceivedDec 26, 2019
  • AcceptedFeb 26, 2020
  • PublishedOct 19, 2020

Abstract

Lovász Local Lemma (LLL) is an important tool in combinatorics and probability theory. It can be used to show the existence of combinatorial objects meeting a collection of criteria as long as the criteria are weakly dependent. It was first proposed by ErdHos and Lovász in 1975. Since then, many applications of LLL have been found in combinatorics, theoretical computer science, and physics. Recently, several new versions of LLL have been proposed. Constructive LLL is an especially big breakthrough in theoretical computer science that has attracted lots of attention. In this paper, we will review recent progress in LLL research, including new versions of LLL and their applications. We will precisely define and differentiate among abstract LLL, lopsided LLL, variable LLL, and quantum LLL. We will also provide connections between abstract LLL and statistical physics, as well as between quantum LLL and quantum physics. LLL can be used to prove the existence of solutions, find solutions efficiently, count the number of solutions, and sample a solution uniformly at random. We will also illustrate these applications of LLL with the SAT problem and the quantum SAT problem.


Funded by

国家自然学基金(61433014,61832003,61761136014,61872334,61801459)

中国科学院战略性先导科技专项(B类)(XDB28000000)

中国科学院王宽诚率先人才计划卢嘉锡国际团队项目


References

[1] ERDHOS P, LOVÁSZ L. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and finite sets, 1975, 10: 609-627. Google Scholar

[2] Alon N, Spencer J H. The Probabilistic Method. 4th ed. Hoboken: John Wiley & Sons, 2016. Google Scholar

[3] SZEGEDY M. The lovász local lemma--a survey. In: Proceedings of International Computer Science Symposium in Russia, Berlin, 2013. 1--11. Google Scholar

[4] Spencer J. Asymptotic lower bounds for Ramsey functions. Discrete Math, 1977, 20: 69-76 CrossRef Google Scholar

[5] Shearer J B. On a problem of spencer. Combinatorica, 1985, 5: 241-245 CrossRef Google Scholar

[6] Gebauer H, SzabÓ T, Tardos G. The local lemma is asymptotically tight for SAT Journal of the ACM (JACM), 2016, 63: 43. Google Scholar

[7] Mcdiarmid C. Hypergraph colouring and the Lovász local lemma. Discrete Mathematics, 1997, 167: 481-486. Google Scholar

[8] Wood D W. The exact location of partition function zeros, a new method for statistical mechanics. J Phys A-Math Gen, 1985, 18: L917-L921 CrossRef ADS Google Scholar

[9] Guttmann A J. COMMENT: Comment on 'The exact location of partition function zeros, a new method for statistical mechanics'. J Phys A-Math Gen, 1987, 20: 511-512 CrossRef ADS Google Scholar

[10] Todo S. Transfer-Matrix Study of Negative-Fugacity Singularity of Hard-Core Lattice Gas. Int J Mod Phys C, 1999, 10: 517-529 CrossRef ADS Google Scholar

[11] SCOTT A D, SOKAL A D. On dependency graphs and the lattice gas. Combinatorics, Probability & Computing, 2006, 15: 253-279. Google Scholar

[12] Bissacot R, Fernández R, Procacci A. An Improvement of the Lovász Local Lemma via Cluster Expansion. Combinator Probab Comp, 2011, 20: 709-719 CrossRef Google Scholar

[13] HARVEY N J, SRIVASTAVA P, VONDRÁK J. Computing the independence polynomial: from the tree threshold down to the roots. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, 2018. 1557--1576. Google Scholar

[14] BezÁkovÁ I, Galanis A, Goldberg L A, et al. Inapproximability of the independent set polynomial in the complex plane. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), Los Angeles, 2018. 1234--1240. Google Scholar

[15] Kolipaka K, Szegedy M, Xu Y. A sharper local lemma with improved applications. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Berlin: Springer, 2012. 603--614. Google Scholar

[16] Erd?s P, Spencer J. Lopsided Lovász Local Lemma and Latin transversals. Discrete Appl Math, 1991, 30: 151-154 CrossRef Google Scholar

[17] Harris D G, Srinivasan A. A constructive lovász local lemma for permutations. Theory of Computing, 2017, 13: 1-41. Google Scholar

[18] SzabÓ S. Transversals of rectangular arrays. Acta Mathematica Universitatis Comenianae, 2008, 77:. Google Scholar

[19] BÖttcher J, Kohayakawa Y, Procacci A. Properly coloured copies and rainbow copies of large graphs with small maximum degree. Random Structures & Algorithms, 2012, 40: 425-436. Google Scholar

[20] Mohr A T. Applications of the lopsided lovász local lemma regarding hypergraphs. Dissertation for Ph.D. Degree. Carolina: University of South Carolina, 2013. Google Scholar

[21] Keevash P, Ku C Y. A random construction for permutation codes and the covering radius. Des Codes Crypt, 2006, 41: 79-86 CrossRef Google Scholar

[22] Lu L, Mohr A, Székely L. Quest for negative dependency graphs. In: Recent Advances in Harmonic Analysis and Applications. Berlin: Springer, 2012. 243--258. Google Scholar

[23] Gebauer H, Moser R A, Scheder D, et al. The Lovász local lemma and satisfiability. In: Efficient Algorithms. Berlin: Springer, 2009. 30--54. Google Scholar

[24] Moitra A. Approximate counting, the lovasz local lemma, and inference in graphical models. Journal of the ACM (JACM), 2019, 66: 10. Google Scholar

[25] Giotis I, Kirousis L, Psaromiligkos K I. Acyclic edge coloring through the Lovász Local Lemma. Theor Comput Sci, 2017, 665: 40-50 CrossRef Google Scholar

[26] Moser R A. A constructive proof of the lovász local lemma. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), Bethesda, 2009. 343--350. Google Scholar

[27] MOSER R A, TARDOS G. A constructive proof of the general Lovász local lemma. Journal of the ACM (JACM), 2010, 57: 11. Google Scholar

[28] Kolipaka K B R, Szegedy M. Moser and Tardos meet Lovász. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), California, 2011. 235--244. Google Scholar

[29] He K, Li L, Liu X, et al. Variable-version Lovász local lemma: Beyond shearer's bound. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), Berkeley, 2017. 451--462. Google Scholar

[30] Rokhsar D S, Kivelson S A. Superconductivity and the quantum hard-core dimer gas. Phys Rev Lett, 1988, 61: 2376-2379 CrossRef ADS Google Scholar

[31] Castelnovo C, Chamon C, Mudry C. From quantum mechanics to classical statistical physics: Generalized Rokhsar-Kivelson Hamiltonians and the "Stochastic Matrix Form" decomposition. Ann Phys, 2005, 318: 316-344 CrossRef ADS arXiv Google Scholar

[32] BRAVYI S. Efficient algorithm for a quantum analogue of 2-sat. Contemporary Mathematics, 2011, 536: 33-48. Google Scholar

[33] AMBAINIS A, KEMPE J, SATTATH O. A quantum Lovász local lemma. Journal of the ACM (JACM), 2012, 59: 24. Google Scholar

[34] He K, Li Q, Sun X, et al. Quantum lovász local lemma: Shearer's bound is tight. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), Phoenix, 2019. 461--472. Google Scholar

[35] Laumann C R, Läuchli A M, Moessner R, et al. On product, generic and random generic quantum satisfiability. Physical Review A, 2010, 81: 359-366. Google Scholar

[36] Sattath O, Morampudi S C, Laumann C R. When a local Hamiltonian must be frustration-free. Proc Natl Acad Sci USA, 2016, 113: 6433-6437 CrossRef ADS arXiv Google Scholar

[37] LAUMANN C, MOESSNER R, SCARDICCHIO A, et al. Phase transitions in random quantum satisfiability. Bulletin of the American Physical Society, 2009, 54. Google Scholar

[38] GILYÉN A, SATTATH O. On preparing ground states of gapped hamiltonians: An efficient quantum Lovász local lemma. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), Berkeley, 2017. 439--450. Google Scholar

[39] BECK J. An algorithmic approach to the Lovász local lemma. Random Structures & Algorithms, 1991, 2: 343-365. Google Scholar

[40] CZUMAJ A, SCHEIDELER C. A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), Portland, 2000. 38--47. Google Scholar

[41] MOLLOY M, REED B. Further algorithmic aspects of the local lemma. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), Dallas, 1998. 524--529. Google Scholar

[42] RADHAKRISHNAN J, SRINIVASAN A. Improved bounds and algorithms for hypergraph 2-coloring. Random Structures & Algorithms, 2000, 16: 4-32. Google Scholar

[43] SALAVATIPOUR M R. A $(1+\epsilon)$-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lovász local lemma. Random Structures & Algorithms, 2004, 25: 68-90. Google Scholar

[44] Messner J, Thierauf T. A Kolmogorov complexity proof of the Lovász Local Lemma for satisfiability. Theor Comput Sci, 2012, 461: 55-64 CrossRef Google Scholar

[45] CATARATA J D, CORBETT S, STERN H, et al. The Moser-Tardos resample algorithm: Where is the limit? (an experimental inquiry). In: Proceedings of the 19th Workshop on Algorithm Engineering and Experiments (ALENEX), Barcelona, 2017. 159--171. Google Scholar

[46] HARVEY N J, VONDRÁK J. An algorithmic proof of the Lovász local lemma via resampling oracles. In: Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS), Berkeley, 2015. 1327--1346. Google Scholar

[47] ACHLIOPTAS D, ILIOPOULOS F. Random walks that find perfect objects and the Lovász local lemma. Journal of the ACM (JACM), 2016, 63: 22. Google Scholar

[48] ACHLIOPTAS D, ILIOPOULOS F. Focused stochastic local search and the Lovász local lemma. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Arlington, 2016. 2024--2038. Google Scholar

[49] ACHLIOPTAS D, ILIOPOULOS F, KOLMOGOROV V. A local lemma for focused stochastic algorithms,. arXiv Google Scholar

[50] KOLMOGOROV V. Commutativity in the algorithmic lovász local lemma. SIAM Journal on Computing, 2018, 47: 2029-2056. Google Scholar

[51] ACHLIOPTAS D, ILIOPOULOS F, SINCLAIR A. Beyond the lovász local lemma: Point to set correlations and their algorithmic applications. In: Proceedings of IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), Baltimore, 2019. 725--744. Google Scholar

[52] HARRIS D G. Deterministic parallel algorithms for fooling polylogarithmic juntas and the lovász local lemma. ACM Transactions on Algorithms (TALG), 2018, 14: 47. Google Scholar

[53] Chandrasekaran K, Goyal N, Haeupler B. Deterministic Algorithms for the Lovász Local Lemma. SIAM J Comput, 2013, 42: 2132-2155 CrossRef Google Scholar

[54] HAEUPLER B, HARRIS D G. Parallel algorithms and concentration bounds for the lovász local lemma via witness dags. ACM Transactions on Algorithms (TALG), 2017, 13: 53. Google Scholar

[55] HARRIS D G. Deterministic algorithms for the lovasz local lemma: simpler, more general, and more parallel,. arXiv Google Scholar

[56] GUO H, JERRUM M, LIU J. Uniform sampling through the lovász local lemma. Journal of the ACM (JACM), 2019, 66: 18. Google Scholar

[57] Guo H, Jerrum M. A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. SIAM J Comput, 2019, 48: 964-978 CrossRef Google Scholar

[58] GUO H, HE K. Tight bounds for popping algorithms,. arXiv Google Scholar

[59] GUO H, JERRUM M. Approximately counting bases of bicircular matroids,. arXiv Google Scholar

[60] FENG W, GUO H, YIN Y, et al. Fast sampling and counting $k$-sat solutions in the local lemma regime,. arXiv Google Scholar

[61] Guo H, Liao C, Lu P. Counting Hypergraph Colorings in the Local Lemma Regime. SIAM J Comput, 2019, 48: 1397-1424 CrossRef Google Scholar

[62] GALANIS A, GOLDBERG L A, GUO H, et al. Counting solutions to random cnf formulas,. arXiv Google Scholar

[63] Bezáková I, Galanis A, Goldberg L A. Approximation via Correlation Decay When Strong Spatial Mixing Fails. SIAM J Comput, 2019, 48: 279-349 CrossRef Google Scholar

[64] CUBITT T S, SCHWARZ M. A constructive commutative quantum lovász local lemma, and beyond,. arXiv Google Scholar

[65] SCHWARZ M, CUBITT T S, VERSTRAETE F. An information-theoretic proof of the constructive commutative quantum Lovász local lemma,. arXiv Google Scholar

[66] SATTATH O, ARAD I. A constructive quantum Lovász local lemma for commuting projectors. Quantum Information & Computation, 2015, 15: 987-996. Google Scholar

[67] Gaunt D S. Hard-Sphere Lattice Gases. II. Plane-Traingular and Three-Dimensional Lattices. J Chem Phys, 1967, 46: 3237-3259 CrossRef ADS Google Scholar

[68] Baxter R J. Hard hexagons: exact solution. J Phys A-Math Gen, 1980, 13: L61-L70 CrossRef ADS Google Scholar

[69] GAUNT D S, FISHER M E. Hard-sphere lattice gases. i. plane-square lattice. The Journal of Chemical Physics, 1965, 43: 2840-2863. Google Scholar

  • Figure 1

    Examples of the dependency graph. (a) Three events; (b) four events

  • Figure 2

    The probability vectors characterized by different LLLs. (a) Theorem 3; (b) Theorem 4; (c) Theorem 9

  • Figure 3

    Examples of the event-variable graph. (a) Three events; (b) four events

  •   

    Algorithm 1 Resample

    Sample $X_1,\ldots,X_n$ uniformly at random;

    while $\exists~i~\in~[m]$ such that $A_i$ holds do

    Choose an arbitrary such $i$ and resample all variables used by $A_i$;

    end while

    Return the current assignments of all variables.

  • Table 1   Relative dimension and independence of vector space
    Probability space $\Omega$ $\rightarrow$ Vector space $V$
    Event $A\subseteq~\Omega$ $\rightarrow$ Subspace $A\subseteq~V$
    Probability $\Pr(A)$ $\rightarrow$ Relative dimension $R(A):=\frac{\dim(A)}{\dim(V)}$
    Conjunction $A\wedge~B$ $\rightarrow$ $A\cap~B$
    Disjunction $A\vee~B$ $\rightarrow$ $A+B=\{a+b|a\in~A,~b\in~B\}$
    Complement $\overline{A}=\Omega\backslash~A$ $\rightarrow$ Orthogonal subspace $A^{\perp}$
    Conditional probability $\Pr(A|B):=\frac{\Pr(A\wedge~B)}{\Pr(B)}$ $\rightarrow$ $R(A|B):=\frac{R(A\cap~B)}{R(B)}$
    Independence $\Pr(A\wedge~B)~=~P(A)\cdot~P(B)$ $\rightarrow$ $R(A\cap~B)=R(A)\cdot~R(B)$
  • Table 2   Summary of the critical thresholds for various lattices
    Lattice Quantum
    Lower bound of the difference
    (between the classical and quantum thresholds)
    Triangular $\frac{5\sqrt{5}~-~11}{2}$ [10,67,68] $6.199\times~10^{-8}$
    Square 0.1193 [10,69] $5.943\times~10^{-8}$
    Hexagonal 0.1547 [10]$1.211\times~10^{-7}$
    Simple cubic 0.0744 [67] $9.533\times~10^{-10}$