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


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}$