DETERMINISTIC ALGORITHMS FOR THE LOVASZ LOCAL LEMMA

被引:35
|
作者
Chandrasekaran, Karthekeyan [1 ,2 ]
Goyal, Navin [3 ]
Haeupler, Bernhard [2 ,4 ]
机构
[1] Georgia Inst Technol, Coll Comp, Atlanta, GA 30332 USA
[2] Microsoft Res, Delhi, India
[3] Microsoft Res, Bangalore 560080, Karnataka, India
[4] MIT, Comp Sci & Artificial Intelligence Lab, Cambridge, MA 02139 USA
关键词
probabilistic method; derandomization; satisfiability; parallelization; PARALLEL ALGORITHM;
D O I
10.1137/100799642
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The Lovasz local lemma (LLL) [P. Erdos and L. Lovasz, Problems and results on 3-chromatic hypergraphs and some related questions, in Infinite and Finite Sets, Vol. II, A. Hajnal, R. Rado, and V. T. Sos, eds., North-Holland, Amsterdam, 1975, pp. 609-627] is a powerful result in probability theory that informally states the following: the probability that none of a set of bad events happens is positive if the probability of each event is small compared to the number of events that depend on it. The LLL is often used for nonconstructive existence proofs of combinatorial structures. A prominent application is to k-CNF formulas, where the LLL implies that if every clause in a formula shares variables with at most d <= 2(k)/(sic) - 1 other clauses, then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment in this setting was given by Moser [A constructive proof of the Lovasz local lemma, in STOC '09: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ACM, New York, 2009, pp. 343-350]. Subsequently Moser and Tardos [J. ACM, 57 (2010), pp. 11:1-11:15] gave a general algorithmic framework for the LLL and a randomized algorithm within this framework to construct the structures guaranteed by the LLL. The main problem left open by Moser and Tardos was to design an efficient deterministic algorithm for constructing structures guaranteed by the LLL. In this paper we provide such an algorithm. Our algorithm works in the general framework of Moser and Tardos with a minimal loss in parameters. For the special case of constructing satisfying assignments for k-CNF formulas with m clauses, where each clause shares variables with at most d <= 2(k/(1+c))/e - 1 other clauses, for any epsilon is an element of (0, 1), we give a deterministic algorithm that finds a satisfying assignment in time (O) over tilde (m(2(1+1/epsilon))). This improves upon the deterministic algorithms of Moser and of Moser and Tardos with running times m(Omega(k2)) and m(Omega(d log d)), respectively, which are superpolynomial for k = omega(1) and d = omega(1), and upon the previous best deterministic algorithm of Beck, which runs in polynomial time only for d <= 2(k/16)/4. Our algorithm is the first deterministic algorithm that works in the general framework of Moser and Tardos. We also give a parallel NC algorithm for the same setting, improving upon an algorithm of Alon [Random Structures Algorithms, 2 (1991), pp. 367-378].
引用
收藏
页码:2132 / 2155
页数:24
相关论文
共 50 条
  • [1] Deterministic Algorithms for the Lovasz Local Lemma
    Chandrasekaran, Karthekeyan
    Goyal, Navin
    Haeupler, Bernhard
    PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2010, 135 : 992 - +
  • [2] Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovasz Local Lemma
    Harris, David G.
    PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2017, : 1188 - 1203
  • [3] Deterministic Parallel Algorithms for Fooling Polylogarithmic Juntas and the Lovasz Local Lemma
    Harris, David G.
    ACM TRANSACTIONS ON ALGORITHMS, 2018, 14 (04)
  • [4] Deterministic algorithms for the Lovasz local lemma: Simpler, more general, and more parallel
    Harris, David G. G.
    RANDOM STRUCTURES & ALGORITHMS, 2023, 63 (03) : 716 - 752
  • [5] Simple Local Computation Algorithms for the General Lovasz Local Lemma
    Achlioptas, Dimitris
    Gouleakis, Themis
    Iliopoulos, Fotis
    PROCEEDINGS OF THE 32ND ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA '20), 2020, : 1 - 10
  • [6] Deterministic counting Lovasz local lemma beyond linear programming
    He, Kun
    Wang, Chunyang
    Yin, Yitong
    PROCEEDINGS OF THE 2023 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2023, : 3388 - 3425
  • [7] Distributed algorithms, the Lovasz Local Lemma, and descriptive combinatorics
    Bernshteyn, Anton
    INVENTIONES MATHEMATICAE, 2023, 233 (02) : 495 - 542
  • [8] Distributed algorithms for the Lovasz local lemma and graph coloring
    Chung, Kai-Min
    Pettie, Seth
    Su, Hsin-Hao
    DISTRIBUTED COMPUTING, 2017, 30 (04) : 261 - 280
  • [9] Distributed Algorithms for the Lovasz Local Lemma and Graph Coloring
    Chung, Kai-Min
    Pettie, Seth
    Su, Hsin-Hao
    PROCEEDINGS OF THE 2014 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'14), 2014, : 134 - 143
  • [10] Improved Distributed Algorithms for the Lovasz Local Lemma and Edge Coloring
    Davies, Peter
    PROCEEDINGS OF THE 2023 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2023, : 4273 - 4295