2019/10/03 by Vladimir Kolmogorov, Kolmogorov, Vladimir
Mathematics · #Advanced Topology and Set Theory #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.1910.01552
openalex publication_date 2019/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider recent formulations of the algorithmic Lovasz Local Lemma by Achlioptas-Iliopoulos-Kolmogorov [2] and by Achlioptas-Iliopoulos-Sinclair [3]. These papers analyze a random walk algorithm for finding objects that avoid undesired "bad events" (or "flaws"), and prove that under certain conditions the algorithm is guaranteed to find a "flawless" object quickly. We show that conditions proposed in these papers are incomparable, and introduce a new family of conditions that includes those in [2, 3] as special cases. We also consider another condition that appeared in [3] in the context of sparse k-SAT formulas. This condition imposes a constraint for each variable of the problem, whereas traditional LLL formulations impose a constraint for each clause. Achlioptas et al. handled the variable-based condition via a reduction to a different condition and then applying a single-clause backtracking algorithm. We propose a new condition that directly captures the sparse k-SAT application considered in [3], and allows the use of the standard local search algorithm (which offers important advantages such as parallelization). Finally, we extend our previous notion of "commutativity" from [20] and prove several implications of commutativity using some new tools that we develop. In particular, we simplify the result of Iliopoulos [16] about approximating the LLL distribution.