The matrix scaling problem, particularly the Sinkhorn–Knopp algorithm, has been studied for over 60 years. In practice, the algorithm often yields high-quality approximations within just a few iterations. Theoretically, however, the best known upper bound on its iteration count scales polynomially with the accuracy parameter \(\varepsilon\), placing it in the class of pseudopolynomial-time approximation algorithms. Meanwhile, the lower-bound landscape remains largely unexplored. Two fundamental questions persist: what accounts for the algorithm's strong empirical performance, and can a tight bound on its iteration count be established?

For an integer b ≥ 0, a b-matching in a graph G = (V, E ) is a set S ⊆ E such that each vertex v ∈ V is incident to at most b edges in S. We design a fully polynomial-time approximation scheme (FPTAS) for counting the number of b-matchings in graphs with bounded degrees. Our FPTAS also applies to a broader family of counting problems, namely Holant problems with log-concave signatures.

In a seminal paper (Moser and Tardos, JACM'10), Moser and Tardos developed a simple and powerful algorithm to find solutions to constraint satisfaction problems. Kolipaka and Szegedy (Kolipaka and Szegedy, STOC'11) proved that the Moser-Tardos algorithm is efficient up to the tight condition of the abstract Lovász Local Lemma, known as Shearer's bound. A fundamental problem around the LLL is whether the efficient region of the Moser-Tardos algorithm can be further extended. In this paper, we give a positive answer to this problem. We show that the efficient region of the Moser-Tardos algorithm indeed goes beyond the Shearer's bound of the underlying dependency graph, if the graph is not chordal. This “chordal condition” is sufficient and necessary, since it has been shown that Shearer's bound exactly characterizes the efficient region for chordal dependency graph (Kolipaka and Szegedy, STOC'11; He, Li, Liu, Wang and Xia, FOCS'17). Moreover, we demonstrate that the efficient region can exceed Shearer's bound by a constant amount by explicitly calculating the gaps on several infinite lattices. The core of our proof is a new criterion on the efficiency of the Moser-Tardos algorithm which takes the intersection between dependent events into consideration. Our criterion is strictly larger than Shearer's bound whenever there exist two dependent events with non-empty intersection. Meanwhile, if any two dependent events are mutually exclusive, our criterion becomes the Shearer's bound, which is known to be tight in this situation for the Moser-Tardos algorithm (Kolipaka and Szegedy, STOC'11; Guo, Jerrum and Liu, JACM'19). * The full version of the paper can be accessed at https://arxiv.org/abs/2111.06527

Let Φ be a random k-CNF formula on n variables and m clauses, where each clause is a disjunction of k literals chosen independently and uniformly. Our goal is, for most Φ, to (approximately) uniformly sample from its solution space. Let α = m/n be the density. The previous best algorithm runs in time npoly(k,α) for any α ≲ 2k/300 [Galanis, Goldberg, Guo, and Yang, SIAM J. Comput.'21]. In contrast, our algorithm runs in almost-linear time for any α ≲ 2k/3.

We give a simple combinatorial algorithm to deterministically approximately count the number of satisfying assignments of general constraint satisfaction problems (CSPs). Suppose that the CSP has domain size q = O(1), each constraint contains at most k = O(1) variables, shares variables with at most Δ = O(1) constraints, and is violated with probability at most p by a uniform random assignment. The algorithm returns in polynomial time in an improved local lemma regime: q2 · κ · p · Δ 5 ≤ C0 for a suitably small absolute constant C0. Here the key term Δ5 improves the previously best known Δ7 for general CSPs [21] and Δ5.714 for the special case of k-CNF [20, 16]. Our deterministic counting algorithm is a derandomization of the very recent fast sampling algorithm in [17]. It departs substantially from all previous deterministic counting Lovasz local lemma algorithms which relied on linear programming, and gives a deterministic approximate counting algorithm that straightforwardly derandomizes a fast sampling algorithm, hence unifying the fast sampling and deterministic approximate counting in the same algorithmic framework. To obtain the improved regime, in our analysis we develop a refinement of the {2, 3}-trees that were used in the previous analyses of counting/sampling LLL. Similar techniques can be applied to the previous LP-based algorithms to obtain the same improved regime and may be of independent interests.

We give a fast algorithm for sampling uniform solutions of general constraint satisfaction problems (CSPs) in a local lemma regime. Ihe expected running time of our algorithm is near-linear in n and a fixed polynomial in $\Delta$, where n is the number of variables and $\Delta$ is the max degree of constraints. Previously, up to similar conditions, sampling algorithms with running time polynomial in both n and $\Delta$, only existed for the almost atomic case, where each constraint is violated by a small number of forbidden local configurations.

We give a Markov chain based algorithm for sampling almost uniform solutions of constraint satisfaction problems (CSPs). Assuming a canonical setting for the Lovász local lemma, where each constraint is violated by a small number of forbidden local configurations, our sampling algorithm is accurate in a local lemma regime, and the running time is a fixed polynomial whose dependency on n is close to linear, where n is the number of variables. Our main approach is a new technique called state compression, which generalizes the “mark/unmark” paradigm of Moitra, and can give fast local-lemma-based sampling algorithms. As concrete applications of our technique, we give the current best almost-uniform samplers for hypergraph colorings and for CNF solutions.

Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all “bad” events under some “weakly dependent” condition. Over the last decades, the algorithmic aspect of LLL has also attracted lots of attention in theoretical computer science. A tight criterion under which the abstract version LLL (ALLL) holds was given by Shearer. It turns out that Shearer’s bound is generally not tight for variable version LLL (VLLL). Recently, Ambainis et al. introduced a quantum version LLL (QLLL), which was then shown to be powerful for the quantum satisfiability problem.

A tight criterion under which the abstract version Lovász Local Lemma (abstract-LLL) holds was given by Shearer [41] decades ago. However, little is known about that of the variable version LLL (variable-LLL) where events are generated by independent random variables, though variable- LLL naturally models and is enough for almost all applications of LLL. We introduce a necessary and sufficient criterion for variable-LLL, in terms of the probabilities of the events and the event-variable graph specifying the dependency among the events. Based on this new criterion, we obtain boundaries for two families of event-variable graphs, namely, cyclic and treelike bigraphs. These are the first two non-trivial cases where the variable-LLL boundary is fully determined. As a byproduct, we also provide a universal constructive method to find a set of events whose union has the maximum probability, given the probability vector and the event-variable graph.Though it is #P-hard in general to determine variable- LLL boundaries, we can to some extent decide whether a gap exists between a variable-LLL boundary and the corresponding abstract-LLL boundary. In particular, we show that the gap existence can be decided without solving Shearer’s conditions or checking our variable-LLL criterion. Equipped with this powerful theorem, we show that there is no gap if the base graph of the event-variable graph is a tree, while gap appears if the base graph has an induced cycle of length at least 4. The problem is almost completely solved except when the base graph has only 3-cliques, in which case we also get partial solutions.A set of reduction rules are established that facilitate to infer gap existence of a event-variable graph from known ones. As an application, various event-variable graphs, in particular combinatorial ones, are shown to be gapful/gapless.