The $f$-divergence is a fundamental notion that measures the difference between two distributions. In this paper, we study the problem of approximating the $f$-divergence between two Ising models, which is a generalization of recent work on approximating the TV-distance. Given two Ising models $ν$ and $μ$, which are specified by their interaction matrices and external fields, the problem is to approximate the $f$-divergence $D_f(ν\,\|\,μ)$ within an arbitrary relative error $\mathrm{e}^{\pm \varepsilon}$. For $χ^α$-divergence with a constant integer $α$, we establish both algorithmic and hardness results. The algorithm works in a parameter regime that matches the hardness result. Our algorithm can be extended to other $f$-divergences such as $α$-divergence, Kullback-Leibler divergence, Rényi divergence, Jensen-Shannon divergence, and squared Hellinger distance.

We study the mixing time of Glauber dynamics on monotone systems. For monotone systems satisfying the entropic independence condition, we prove a new mixing time comparison result for Glauber dynamics. For concrete applications, we obtain \(\tilde O(n)\) mixing time for the random cluster model induced by the ferromagnetic Ising model with consistently biased external fields, and \(\tilde O(n^2)\) mixing time for the bipartite hardcore model under the one-sided uniqueness condition, where \(n\) is the number of variables in corresponding models, improving the best known results in [Chen and Zhang, SODA’23] and [Chen, Liu, and Yin, FOCS’23], respectively.

We study the problem of learning an n-variables k-CNF formula Φ from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) with k-wise hard constraints. Revisiting Valiant’s algorithm (Commun. ACM’84), we show that it can exactly learn (1) k-CNFs with bounded clause intersection size under Lovász local lemma type conditions, from O(logn) samples; and (2) random k-CNFs near the satisfiability threshold, from O(nexp(−√k)) samples. These results significantly improve the previous O(nk) sample complexity. We further establish new information-theoretic lower bounds on sample complexity for both exact and approximate learning from uniform random solutions.

The total variation distance is a metric of central importance in statistics and probability theory. However, somewhat surprisingly, questions about computing it \emph{algorithmically} appear not to have been systematically studied until very recently. In this paper, we contribute to this line of work by studying this question in the important special case of multivariate Gaussians. More formally, we consider the problem of approximating the total variation distance between two multivariate Gaussians to within an $\epsilon$-relative error. Previous works achieved a \emph{fixed} constant relative error approximation via closed-form formulas. In this work, we give algorithms that given any two $n$-dimensional Gaussians $D_1,D_2$, and any error bound $\epsilon > 0$, approximate the total variation distance $D := d_{TV}(D_1,D_2)$ to $\epsilon$-relative accuracy in $\mathrm{poly}(n,\frac{1}{\epsilon},\log \frac{1}{D})$ operations. The main technical tool in our work is a reduction that helps us extend the recent progress on computing the TV-distance between \emph{discrete} random variables to our continuous setting.

We develop a new framework to prove the mixing or relaxation time for the Glauber dynamics on spin systems with unbounded degree. It works for general spin systems including both 2-spin and multi-spin systems. As applications for this approach: - We prove the optimal O(n) relaxation time for the Glauber dynamics of random q-list-coloring on an n-vertices triangle-tree graph with maximum degree Δ such that q/Δ > α^⋆, where α^⋆ ≈ 1.763 is the unique positive solution of the equation α = exp(1/α). This improves the n^{1+o(1)} relaxation time for Glauber dynamics obtained by the previous work of Jain, Pham, and Vuong (2022). Besides, our framework can also give a near-linear time sampling algorithm under the same condition. - We prove the optimal O(n) relaxation time and near-optimal Õ(n) mixing time for the Glauber dynamics on hardcore models with parameter λ in balanced bipartite graphs such that λ < λ_c(Δ_L) for the max degree Δ_L in left part and the max degree Δ_R of right part satisfies Δ_R = O(Δ_L). This improves the previous result by Chen, Liu, and Yin (2023). At the heart of our proof is the notion of coupling independence which allows us to consider multiple vertices as a huge single vertex with exponentially large domain and do a "coarse-grained" local-to-global argument on spin systems. The technique works for general (multi) spin systems and helps us obtain some new comparison results for Glauber dynamics.

Spin systems form an important class of undirected graphical models. For two Gibbs distributions $\mu$ and $\nu$ induced by two spin systems on the same graph $G = (V, E)$, we study the problem of approximating the total variation distance $d_{\mathrm{TV}}\left({\mu},{\nu}\right)$ with an $\epsilon$-relative error. We propose a new reduction that connects the problem of approximating the TV-distance to sampling and approximate counting. Our applications include the hardcore model and the antiferromagnetic Ising model in the uniqueness regime, the ferromagnetic Ising model, and the general Ising model satisfying the spectral condition. Additionally, we explore the computational complexity of approximating the total variation distance $d_{\mathrm{TV}}\left({\mu_S},{\nu_S}\right)$ between two marginal distributions on an arbitrary subset $S \subseteq V$. We prove that this problem remains hard even when both $\mu$ and $\nu$ admit polynomial-time sampling and approximate counting algorithms.

We show that the flip chain for non-crossing spanning trees of n+1 points in convex position mixes in time O(n⁸log n). We use connections between Fuss-Catalan structures to construct a comparison argument with a chain similar to Wilson’s lattice path chain (Wilson 2004).

We show that spin systems with bounded degrees and coupling independence admit fully polynomial time approximation schemes (FPTAS). We design a new recursive deterministic counting algorithm to achieve this. As applications, we give the first FPTASes for q-colourings on graphs of bounded maximum degree $\Delta \geq 3$, when $q \geq\left(11 / 6-\varepsilon_{0}\right) \Delta$ for some small $\varepsilon_{0} \approx 10^{-5}$, or when $\Delta \geq 125$ and $q \geq 1.809 \Delta$, and on graphs with sufficiently large (but constant) girth, when $q \geq \Delta+3$. These bounds match the current best randomised approximate counting algorithms by Chen, Delcourt, Moitra, Perarnau, and Postle (2019), Carlson and Vigoda (2024), and Chen, Liu, Mani, and Moitra (2023), respectively.

We show that the Jerrum-Sinclair Markov chain on matchings mixes in time $\widetilde{O}\left(\Delta^{2} m\right)$ on any graph with n vertices, m edges, and maximum degree $\Delta$, for any constant edge weight $\lambda\gt 0$. For general graphs with arbitrary, potentially unbounded $\Delta$, this provides the first improvement over the classic $\widetilde{O}\left(n^{2} m\right)$ mixing time bound of Jerrum and Sinclair (1989) and Sinclair (1992). To achieve this, we develop a general framework for analyzing mixing times, combining ideas from the classic canonical path method with the “local-to-global” approaches recently developed in high-dimensional expanders, introducing key innovations to both techniques.

We revisit the classic #Knapsack problem, which asks to count the Boolean points (x1, x2, …, xn ) ∈ {0,1}n in a given half-space . This #P-complete problem is known to admit (1 ± ∊)-approximation. Before this work, [Dyer, STOC 2003]’s Õ (n2 5 + n2∊-2)-time randomized approximation scheme remains the fastest known in the natural regime of ε ≥ 1/ poly log n.

We address the convergence rate of Markov chains for randomly generating an edge coloring of a given tree. Our focus is on the Glauber dynamics which updates the color at a randomly chosen edge in each step. For a tree T with n vertices and maximum degree Δ, when the number of colors q satisfies q ≥ Δ + 2 then we prove that the Glauber dynamics has an optimal relaxation time of O (n), where the relaxation time is the inverse of the spectral gap. This is optimal in the range of q in terms of Δ as Dyer, Goldberg, and Jerrum (2006) showed that the relaxation time is Ω(n3) when q = Δ + 1. For the case q = Δ + 1, we show that an alternative Markov chain which updates a pair of neighboring edges has relaxation time O (n ). Moreover, for the Δ-regular complete tree we prove O (n log2 n ) mixing time bounds for the respective Markov chain. Our proofs establish approximate tensorization of variance via a novel inductive approach, where the base case is a tree of height ℓ = O (Δ2 log2 Δ), which we analyze using a canonical paths argument.

Abstract. We present a new framework to derandomize certain Markov chain Monte Carlo (MCMC) algorithms. As in MCMC, we first reduce counting problems to sampling from a sequence of marginal distributions. For the latter task, we introduce a method called coupling toward the past that can, in logarithmic time, evaluate one or a constant number of variables from a stationary Markov chain state. Since there are at most logarithmic random choices, this leads to very simple derandomization. As an application, we provide an efficient deterministic approximate counting algorithm for hypergraph independent sets, under local lemma type conditions matching, up to lower-order factors, their state-of-the-art randomized counterparts.

We give a fully polynomial-time randomized approximation scheme (FPRAS) for two terminal reliability in directed acyclic graphs (DAGs). In contrast, we also show the complementing problem of approximating two terminal unreliability in DAGs is #BIS-hard.

We present two randomised approximate counting algorithms with Oe(n2−c/ε2) running time for some constant c > 0 and accuracy ε: 1. for the hard-core model with fugacity λ on graphs with maximum degree ∆ when λ = O(∆−1.5−c1) where c1 = c/(2 − 2c); 2. for spin systems with strong spatial mixing (SSM) on planar graphs with quadratic growth, such as Z2. For the hard-core model, Weitz’s algorithm (STOC, 2006) achieves sub-quadratic running time when correlation decays faster than the neighbourhood growth, namely when λ = o(∆−2). Our first algorithm does not require this property and extends the range where sub-quadratic algorithms exist. Our second algorithm appears to be the first to achieve sub-quadratic running time up to the SSM threshold, albeit on a restricted family of graphs. It also extends to (not necessarily planar) graphs with polynomial growth, such as Zd, but with a running time of the form O (n2ε−2/2c(log n)1/d) where d is the exponent of the polynomial growth and c > 0 is some constant.

Total variation distance (TV distance) is an important measure for the difference between two distributions.

We present a new framework to derandomise certain Markov chain Monte Carlo (MCMC) algorithms. As in MCMC, we first reduce counting problems to sampling from a sequence of marginal distributions. For the latter task, we introduce a method called coupling towards the past that can, in logarithmic time, evaluate one or a constant number of variables from a stationary Markov chain state. Since there are at most logarithmic random choices, this leads to very simple derandomisation. We provide two applications of this framework, namely efficient deterministic approximate counting algorithms for hypergraph independent sets and hypergraph colourings, under local lemma type conditions matching, up to lower order factors, their state-of-the-art randomised counterparts.

We study the single-site Glauber dynamics for the fugacity λ, Hard-Core model on the random graph G(n, d/n). We show that for the typical instances of the random graph G(n, d/n) and for dd fugacity λ <(d−1)d+1, the mixing time of Glauber dynamics is n1+O(1/ log log n) . Our result improves on the recent elegant algorithm in [Bezáková, Galanis, Goldberg and Štefankovič; ICALP’22]. The algorithm there is an MCMC-based sampling algorithm, but it is not the Glauber dynamics. Our algorithm here is simpler, as we use the classic Glauber dynamics. Furthermore, the bounds on mixing time we prove are smaller than those in Bezáková et al. paper, hence our algorithm is also faster. The main challenge in our proof is handling vertices with unbounded degrees. We provide stronger results with regard the spectral independence via branching values and show that the our Gibbs distributions satisfy the approximate tensorisation of the entropy. We conjecture that the bounds we have here are optimal for G(n, d/n). As corollary of our analysis for the Hard-Core model, we also get bounds on the mixing time of the Glauber dynamics for the Monomer-Dimer model on G(n, d/n). The bounds we get for this model are slightly better than those we have for the Hard-Core model.

We study the sampling problem for the ferromagnetic Ising model with consistent external fields, and in particular, Swendsen-Wang dynamics on this model. We introduce a new grand model unifying two closely related models: the subgraph world and the random cluster model. Through this new viewpoint, we show: polynomial mixing time bounds for Swendsen-Wang dynamics and (edge-flipping) Glauber dynamics of the random cluster model, generalising the bounds and simplifying the proofs for the no-field case by Guo and Jerrum (2018); near linear mixing time for the two dynamics above if the maximum degree is bounded and all fields are (consistent and) bounded away from 1.

We study the problem of sampling almost uniform proper q-colourings in k-uniform simple hypergraphs with maximum degree Δ. For any δ>0, if k≥20(1+δ)δ and q≥100Δ2+δk−4/δ−4, the running time of our algorithm is O~(poly(Δk)⋅n1.01), where n is the number of vertices. Our result requires fewer colours than previous results for general hypergraphs (Jain, Pham, and Voung, 2021; He, Sun, and Wu, 2021), and does not require Ω(logn) colours unlike the work of Frieze and Anastos (2017).

We prove an optimal $\Omega(n^{-1})$ lower bound for modified $\log$-Sobolev (MLS) constant of the Glauber dynamics for anti-ferromagnetic two-spin systems with n vertices in the tree uniqueness regime. Specifically, this optimal MLS bound holds for the following classes of two-spin systems in the tree uniqueness regime: (1) all strictly anti-ferromagnetic two-spin systems (where both edge parameters $\beta, \gamma\leq$ 1), which cover the hardcore models and the anti-ferromagnetic Ising models; (2) general antiferromagnetic two-spin systems on regular graphs. Consequently, an optimal $O(n\log n)$ mixing time holds for these anti-ferromagnetic two-spin systems when the uniqueness condition is satisfied. These MLS and mixing time bounds hold for any bounded or unbounded maximum degree, and the constant factors in the bounds depend only on the gap to the uniqueness threshold. We prove this by showing a boosting theorem for MLS constant for distributions satisfying certain spectral independence and marginal stability properties.

We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ 4 ]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper q -colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided q ≥ ( α * + δ )Δ where α * ≈ 1.763 is the unique solution to α * = exp (1/ α * ) and δ Þ 0 is any constant. This is the first efficient algorithm for sampling proper q -colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [ 25 ].

We prove an optimal$\Omega(n^{-1})$lower bound on the spectral gap of Glauber dynamics for anti-ferromagnetic two-spin systems with$n$vertices in the tree uniqueness regime. This spectral gap holds for any, including unbounded, maximum degree Δ. Consequently, we have the following mixing time bounds for the models satisfying the uniqueness condition with a slack$\delta\in(0,1)$: •$C(\delta)n^{2}\log n$mixing time for the hardcore model with fugacity$\leq(1-\delta)\lambda_{c}(\Delta)=(1-\delta)\frac{(\Delta-1)^{\Delta-1}}{(\Delta-2)^{\Delta}}$; •$C(\delta)n^{2}$mixing time for the Ising model with edge activity$\beta\in[\frac{\Delta-2+\delta}{\Delta-\delta},\frac{\Delta-\delta}{\Delta-2+\delta}]$; where the maximum degree Δ may depend on the number of vertices n, and C(δ) depends only on δ. Our proof is built upon the recently developed connections between the Glauber dynamics for spin systems and the high-dimensional expander walks. In particular, we prove a stronger notion of spectral independence, called the complete spectral independence, and use a novel Markov chain called the field dynamics to connect this stronger spectral independence to the rapid mixing of Glauber dynamics for all degrees.

We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [2]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper q-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided q ≥ (α∗ + δ)Δ where α∗ ≈ 1.763 is the unique solution to α∗ = exp (1/α∗) and δ > 0 is any constant. This is the first efficient algorithm for sampling proper q-colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [19].

The Metropolis-Hastings algorithm is a fundamental Markov chain Monte Carlo (MCMC) method for sampling and inference. With the advent of Big Data, distributed and parallel variants of MCMC methods are attracting increased attention. In this paper, we give a distributed algorithm that can faithfully simulates sequential single-site Metropolis chains without introducing any bias. When a natural Lipschitz condition for the the Metropolis filters is satisfied, the algorithm can faithfully simulate N-step Metropolis chains within O(N/n + log n) rounds of asynchronous communications, where n is the number of variables. For sequential single-site dynamics, whose mixing requires Ω(n log n) steps, this achieves an optimal linear speedup. For several well-studied graphical models, including proper graph coloring, hardcore model, and Ising model, our condition for linear speedup is much weaker than the uniqueness conditions for the respective models. The novel idea in our algorithm is to resolve updates in advance: the local Metropolis filters can be executed correctly before the full information about neighboring spins is available. This achieves optimal parallelism without introducing any bias.

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.

We give new algorithms based on Markov chains to sample and approximately count satisfying assignments to k -uniform CNF formulas where each variable appears at most d times. For any k and d satisfying kd < n o(1) and k ≥ 20 log k + 20 log d + 60, the new sampling algorithm runs in close to linear time, and the counting algorithm runs in close to quadratic time. Our approach is inspired by Moitra (JACM, 2019), which remarkably utilizes the Lovász local lemma in approximate counting. Our main technical contribution is to use the local lemma to bypass the connectivity barrier in traditional Markov chain approaches, which makes the well-developed MCMC method applicable on disconnected state spaces such as SAT solutions. The benefit of our approach is to avoid the enumeration of local structures and obtain fixed polynomial running times, even if k = ω (1) or d = ω (1).

In this paper, we study the problem of sampling from a graphical model when the model itself is changing dynamically with time. This problem derives its interest from a variety of inference, learning, and sampling settings in machine learning, computer vision, statistical physics, and theoretical computer science. While the problem of sampling from a static graphical model has received considerable attention, theoretical works for its dynamic variants have been largely lacking. The main contribution of this paper is an algorithm that can sample dynamically from a broad class of graphical models over discrete random variables. Our algorithm is parallel and Las Vegas: it knows when to stop, and it outputs samples from the exact distribution. We also provide sufficient conditions under which this algorithm runs in time proportional to the size of the update on general graphical models as well as well-studied specific spin systems. In particular we obtain, for the Ising model (ferromagnetic or antiferromagnetic) and for the hardcore model the first dynamic sampling algorithms that can handle both edge and vertex updates (addition, deletion, and change of functions). The algorithms for both these models are efficient within regimes that are close to the respective uniqueness regimes, beyond which, even for the static and approximate sampling, no local algorithms were known or the problem itself is intractable. Our dynamic sampling algorithm relies on a local resampling algorithm and a new “equilibrium" property that is shown to be satisfied by our algorithm at each step and enables us to prove its correctness. This equilibrium property is robust enough to guarantee the correctness of our algorithm, helps us improve bounds on fast convergence on specific models, and should be of independent interest.

We give new algorithms based on Markov chains to sample and approximately count satisfying assignments to k-uniform CNF formulas where each variable appears at most d times. For any k and d satisfying kd

The local computation of Linial [FOCS’87] and Naor and Stockmeyer [STOC’93] studies whether a locally defined distributed computing problem is locally solvable. In classic local computation tasks, the goal of distributed algorithms is to construct a feasible solution for some constraint satisfaction problem (CSP) locally defined on the network. In this paper, we consider the problem of sampling a uniform CSP solution by distributed algorithms in the $$\mathsf {LOCAL}$$ model, and ask whether a locally definable joint distribution is locally sample-able. We use Markov random fields and Gibbs distributions to model locally definable joint distributions. We give two distributed algorithms based on Markov chains, called LubyGlauber and LocalMetropolis, which we believe to represent two basic approaches for distributed Gibbs sampling. The algorithms achieve respective mixing times $$O(\varDelta \log n)$$ and $$O(\log n)$$ under typical mixing conditions, where n is the number of vertices and $$\varDelta $$ is the maximum degree of the graph. We show that the time bound $$\varTheta (\log n)$$ is optimal for distributed sampling. We also show a strong $$\varOmega (\mathrm {diam})$$ lower bound: in particular for sampling independent set in graphs with maximum degree $$\varDelta \ge 6$$ . This gives a strong separation between sampling and constructing locally checkable labelings.

In this paper, we study the problem of sampling from a graphical model when the model itself is changing dynamically with time. This problem derives its interest from a variety of inference, learning, and sampling settings in machine learning, computer vision, statistical physics, and theoretical computer science. While the problem of sampling from a static graphical model has received considerable attention, theoretical works for its dynamic variants have been largely lacking. The main contribution of this paper is an algorithm that can sample dynamically from a broad class of graphical models over discrete random variables. Our algorithm is parallel and Las Vegas: it knows when to stop and it outputs samples from the exact distribution. We also provide sufficient conditions under which this algorithm runs in time proportional to the size of the update, on general graphical models as well as well-studied specific spin systems. In particular we obtain, for the Ising model (ferromagnetic or anti-ferromagnetic) and for the hardcore model the first dynamic sampling algorithms that can handle both edge and vertex updates (addition, deletion, change of functions), both efficient within regimes that are close to the respective uniqueness regimes, beyond which, even for the static and approximate sampling, no local algorithms were known or the problem itself is intractable. Our dynamic sampling algorithm relies on a local resampling algorithm and a new ``equilibrium'' property that is shown to be satisfied by our algorithm at each step, and enables us to prove its correctness. This equilibrium property is robust enough to guarantee the correctness of our algorithm, helps us improve bounds on fast convergence on specific models, and should be of independent interest.

In classic distributed graph problems, each instance on a graph specifies a space of feasible solutions (e.g. all proper (Δ + 1)-listcolorings of the graph), and the task of distributed algorithm is to construct a feasible solution using local information.

The local computation of Linial [FOCS'87] and Naor and Stockmeyer [STOC'93] concerns with the question of whether a locally definable distributed computing problem can be solved locally: more specifically, for a given local CSP (Constraint Satisfaction Problem) whether a CSP solution can be constructed by a distributed algorithm using local information. In this paper, we consider the problem of sampling a uniform CSP solution by distributed algorithms, and ask whether a locally definable joint distribution can be sampled from locally. More broadly, we consider sampling from Gibbs distributions induced by weighted local CSPs, especially the Markov random fields (MRFs), in the LOCAL model. We give two Markov chain based distributed algorithms which we believe to represent two fundamental approaches for sampling from Gibbs distributions via distributed algorithms. The first algorithm generically parallelizes the single-site sequential Markov chain by updating in each step the variables from a random independent set in parallel, and achieves an O(Δ log n) time upper bound in the LOCAL model, where Δ is the maximum degree, when the Dobrushin's condition for the Gibbs distribution is satisfied. The second algorithm is a novel parallel Markov chain which proposes to update all variables simultaneously yet still guarantees to converge correctly with no bias. It surprisingly parallelizes an intrinsically sequential process: stabilizing to a joint distribution with massive local dependencies, and may achieve an optimal O(log n) time upper bound independent of the maximum degree Δ under a stronger mixing condition.