The Coupling from the Past (CFTP) paradigm is a canonical method for perfect sampling. For uniform sampling of proper q-colorings in graphs with maximum degree Δ, the bounding chains of [Huber, STOC '98] provide a systematic framework for efficiently implementing CFTP algorithms within the classical regime q ≥ (1+o(1))Δ². This was subsequently improved to q > 3Δ by [Bhandari and Chakraborty, STOC '20] and to q ≥ (8/3 + o(1))Δ by [Jain, Sah, and Sawhney, STOC '21]. In this work, we establish the asymptotically tight threshold for bounding-chain-based CFTP algorithms for graph colorings. We prove a lower bound showing that all such algorithms satisfying the standard contraction property require q ≥ 2.5Δ, and we present an efficient CFTP algorithm that achieves this asymptotically optimal threshold q ≥ (2.5 + o(1))Δ via an optimal design of bounding chains.

The notion of Las Vegas algorithms was introduced by Babai (1979) and can be defined in two ways: * In Babai's original definition, a randomized algorithm is called Las Vegas if it has a finitely bounded running time and certifiable random failure. * Another definition widely accepted today is that Las Vegas algorithms refer to zero-error randomized algorithms with random running times. The equivalence between the two definitions is straightforward. Specifically, for randomized algorithms with certifiable failures, repeatedly running the algorithm until no failure is encountered allows for faithful simulation of the correct output when it executes successfully. We show that a similar perfect simulation can also be achieved in distributed local computation. Specifically, in the LOCAL model, with polylogarithmic overhead in time complexity, any Las Vegas algorithm with finitely bounded running time and locally certifiable failures can be converted to a zero-error Las Vegas algorithm. This transformed algorithm faithfully reproduces the correct output of the original algorithm in successful executions.

Local samplers are algorithms that generate random samples based on local queries to high-dimensional distributions, ensuring the samples follow the correct induced distributions while maintaining time complexity that scales locally with the query size. These samplers have broad applications, including deterministic approximate counting [He, Wang, Yin, SODA ’23; Feng et.al., FOCS ’23], sampling from infinite or high-dimensional Gibbs distributions [Anand, Jerrum, SICOMP ’22; He, Wang, Yin, FOCS ’22], and providing local access to large random objects [Biswas, Rubinfield, Yodpinyanee, ITCS ’20].

The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sampling is based on simulated annealing. In this approach, the counting problem is formulated as estimating the ratio Q = Z(βmax)/Z(βmin) between partition functions Z(β) = Σx∈Ω exp(βH(x)) of Gibbs distributions μβ over Ω with Hamiltonian H, given access to a sampling oracle for μβ at any β ∈ [βmin, βmax]. The sample complexity (measured by the number of oracle calls) is typically expressed in terms of q and h, which respectively bound ln Q and H. The best upper bound achieved by known annealing algorithms with relative error ε is O(qε−2 log h). However, all known algorithms attaining this near-optimal complexity are inherently sequential, or adaptive: the queried parameters β depend on previous samples.

We introduce efficient parallel algorithms for sampling from the Gibbs distribution and estimating the partition function of Ising models. These algorithms achieve parallel efficiency, with polylogarithmic depth and polynomial total work, and are applicable to Ising models in the following regimes: (1) Ferromagnetic Ising models with external fields; (2) Ising models with interaction matrix $J$ of operator norm $\|J\|_2<1$. Our parallel Gibbs sampling approaches are based on localization schemes, which have proven highly effective in establishing rapid mixing of Gibbs sampling. In this work, we employ two such localization schemes to obtain efficient parallel Ising samplers: the \emph{field dynamics} induced by \emph{negative-field localization}, and \emph{restricted Gaussian dynamics} induced by \emph{stochastic localization}. This shows that localization schemes are powerful tools, not only for achieving rapid mixing but also for the efficient parallelization of Gibbs sampling.

The hardcore model is a fundamental probabilistic model extensively studied in statistical physics, probability theory, and computer science. It defines a Gibbs distribution over independent sets of a given graph, parameterized by a vertex activity λ > 0. For graphs of maximum degree ∆, a well-known computational phase transition occurs at the tree-uniqueness threshold ${\lambda _c}(\Delta ) = \frac{{{{(\Delta - 1)}^{\Delta - 1}}}}{{{{(\Delta - 2)}^\Delta }}}$, where the mixing behavior of the Glauber dynamics (a simple Markov chain) undergoes a sharp transition: it mixes in nearly linear time for λc(∆), in polynomial but super-linear time at λ = λc(∆), and experiences exponential slowdown for λ > λc(∆).It is conjectured that random regular graphs exhibit different mixing behavior, with the slowdown occurring far beyond the uniqueness threshold. We confirm this conjecture by showing that, for the hardcore model on random ∆-regular graphs, the Glauber dynamics mixes rapidly with high probability when $\lambda = O\left( {1/\sqrt \Delta } \right)$, which is significantly beyond the uniqueness threshold λc(∆) ≈ e/∆. Our result establishes a sharp distinction between the hardcore model on worst-case and beyond-worst-case instances, showing that the worst-case and average-case complexities of sampling and counting are fundamentally different.This result of rapid mixing on random instances follows from a new criterion we establish for rapid mixing of Glauber dynamics for any distribution supported on a downward closed set family. Our criterion is simple, general, and easy to check. In addition to proving new mixing conditions for the hardcore model, we also establish improved mixing time bounds for sampling uniform matchings or b-matchings on graphs, the random cluster model on matroids with q ∈ [0,1), and the determinantal point process. Our proof of this new criterion for rapid mixing combines and generalizes several recent tools in a novel way, including a trickle-down theorem for field dynamics, spectral/entropic stability, and a new comparison result between field dynamics and Glauber dynamics.

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 study how to establish spectral independence, a key concept in sampling, without relying on total influence bounds, by applying an approximate inverse of the influence matrix. Our method gives constant upper bounds on spectral independence for two well-studied Gibbs distributions known to have unbounded total influences:

Single-site dynamics are canonical Markov chain based algorithms for sampling from high-dimensional distributions, such as the Gibbs distributions of graphical models. We introduce a simple and generic parallel algorithm that faithfully simulates single-site dynamics. Under a much relaxed, asymptotic variant of the ℓ p -Dobrushin’s condition—where the Dobrushin’s influence matrix has a bounded ℓ p -induced operator norm for an arbitrary p ∈ [1, ∞]—our algorithm simulates N steps of single-site updates within a parallel depth of O ( N / n +log n ) on Õ( m ) processors, where n is the number of sites and m is the size of the graphical model. For Boolean-valued random variables, if the ℓ p -Dobrushin’s condition holds—specifically, if the ℓ p -induced operator norm of the Dobrushin’s influence matrix is less than 1—the parallel depth can be further reduced to O (log N + log n ), achieving an exponential speedup. These results suggest that single-site dynamics with near-linear mixing times can be parallelized into RNC sampling algorithms, independent of the maximum degree of the underlying graphical model, as long as the Dobrushin influence matrix maintains a bounded operator norm. We show the effectiveness of this approach with RNC samplers for the hardcore and Ising models within their uniqueness regimes, as well as an RNC SAT sampler for satisfying solutions of conjunctive normal form formulas in a local lemma regime. Furthermore, by employing non-adaptive simulated annealing, these RNC samplers can be transformed into RNC algorithms for approximate counting.

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 present polynomial-time algorithms for approximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regime: \begin{equation*} pD^{2+o_{q}(1)}\lesssim 1.\end{equation*} When the domain size$q$of each variable becomes sufficiently large, this almost matches the known lower bound$pD^{2}\lesssim 1$for approximate counting and sampling solutions to atomic CSPs [1], [2], thus establishing an almost tight sampling Lovasz local lemma for large domain sizes.

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 characterize the uniqueness condition in the hardcore model for bipartite graphs with degree bounds only on one side, and provide a nearly linear time sampling algorithm that works up to the uniqueness threshold. We show that the uniqueness threshold for bipartite graph has almost the same form of the tree uniqueness threshold for general graphs, except with degree bounds only on one side of the bipartition. The hardcore model is originated in statistical physics for modeling equilibrium of lattice gas. Combinatorially, it can also be seen as a weighted enumeration of independent sets. Counting the number of independent sets in a bipartite graph (#BIS) is a central open problem in approximate counting. Compared to the same problem in a general graph, surprising tractable regime have been identified that are believed to be hard in general. This is made possible by two lines of algorithmic approach: the high-temperature algorithms starting from Liu and Lu (STOC 2015), and the low-temperature algorithms starting from Helmuth, Perkins, and Regts (STOC 2019).In this work, we study the limit of these algorithms in the high-temperature case. Our characterization of the uniqueness condition is obtained by proving decay of correlations for arguably the best possible regime, which involves locating fixpoints of multivariate iterative rational maps and showing their contraction. Interestingly, we are able to show that a regime that was considered “low-temperature” is actually well within the uniqueness (high-temperature) regime. We also give a nearly linear time sampling algorithm based on simulating field dynamics only on one side of the bipartite graph that works up to the uniqueness threshold. Our algorithm is very different from the original high-temperature algorithm of Liu and Lu (STOC 2015), and it makes use of a connection between correlation decay and spectral independence of Markov chains. Along the way, we also build an explicit connection between the very recent developments of negative-fields stochastic localization schemes and field dynamics. Last but not the least, we are able to show that the standard Glauber dynamics on both side of the bipartite graph mixes in polynomial time up to the uniqueness. Remarkably, this is a model where both the total influence and the spectral radius of the adjacency matrix can be unbounded, yet we are able to prove mixing time bounds through the framework of spectral independence.

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 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 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.

The single-site dynamics are a canonical class of Markov chains for sampling from high-dimensional probability distributions, e.g. the ones represented by graphical models.

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.

The membership problem asks to maintain a set $S\subseteq[u]$, supporting insertions and membership queries, i.e., testing if a given element is in the set. A data structure that computes exact answers is called a dictionary. When a (small) false positive rate $ε$ is allowed, the data structure is called a filter. The space usages of the standard dictionaries or filters usually depend on the upper bound on the size of $S$, while the actual set can be much smaller. Pagh, Segev and Wieder (FOCS'13) were the first to study filters with varying space usage based on the current $|S|$. They showed in order to match the space with the current set size $n=|S|$, any filter data structure must use $(1-o(1))n(\log(1/ε)+(1-O(ε))\log\log n)$ bits, in contrast to the well-known lower bound of $N\log(1/ε)$ bits, where $N$ is an upper bound on $|S|$. They also presented a data structure with almost optimal space of $(1+o(1))n(\log(1/ε)+O(\log\log n))$ bits provided that $n>u^{0.001}$, with expected amortized constant insertion time and worst-case constant lookup time. In this work, we present a filter data structure with improvements in two aspects: - it has constant worst-case time for all insertions and lookups with high probability; - it uses space $(1+o(1))n(\log (1/ε)+\log\log n)$ bits when $n>u^{0.001}$, achieving optimal leading constant for all $ε=o(1)$. We also present a dictionary that uses $(1+o(1))n\log(u/n)$ bits of space, matching the optimal space in terms of the current size, and performs all operations in constant time with high probability.

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.

We study the problem of approximately counting matchings in hypergraphs of bounded maximum degree and maximum size of hyperedges. With an activity parameter λ , each matching M is assigned a weight λ | M | . The counting problem is formulated as computing a partition function that gives the sum of the weights of all matchings in a hypergraph. This problem unifies two extensively studied statistical physics models in approximate counting: the hardcore model (graph independent sets) and the monomer–dimer model (graph matchings). For this problem, the critical activity λ c = d d k ( d − 1 ) d + 1 is the threshold for the uniqueness of Gibbs measures on the infinite ( d + 1 ) -uniform ( k + 1 ) -regular hypertree. Consider hypergraphs of maximum degree at most k + 1 and maximum size of hyperedges at most d + 1 . We show that when λ < λ c , there is an FPTAS for computing the partition function; and when λ = λ c , there is a PTAS for computing the log-partition function. These algorithms are based on the decay of correlation (strong spatial mixing) property of Gibbs distributions. When λ > 2 λ c , there is no PRAS for the partition function or the log-partition function unless NP = RP. Towards obtaining a sharp transition of computational complexity of approximate counting, we study the local convergence from a sequence of finite hypergraphs to the infinite lattice with specified symmetry. We show a surprising connection between the local convergence and the reversibility of a natural random walk. This leads us to a barrier for the hardness result: The non-uniqueness of infinite Gibbs measure is not realizable by any finite gadgets.

We study the hard-core (gas) model defined on independent sets of an input graph where the independent sets are weighted by a parameter (aka fugacity) $\lambda>0$. For constant $\Delta$, the previous work of Weitz [ Proceedings of STOC, 2006, pp. 140--149] established an FPTAS for the partition function for graphs of maximum degree $\Delta$ when $\lambda<\lambda_c(\Delta)$. Sly [ Proceedings of FOCS, 2010, pp. 287--296] showed that there is no FPRAS, unless NP=RP, when $\lambda>\lambda_c(\Delta)$. The threshold $\lambda_c(\Delta)$ is the critical point for the statistical physics phase transition for uniqueness/nonuniqueness on the infinite $\Delta$-regular tree. The running time of Weitz's algorithm is exponential in $\log{\Delta}$. Here we present an FPRAS for the partition function whose running time is $O^*(n^2)$. We analyze the simple single-site Markov chain known as the Glauber dynamics for sampling from the associated Gibbs distribution. We prove there exists a constant $\Delta_0$ such that for all graphs with maximum degree $\Delta\geq\Delta_0$ and girth $\geq 7$ (i.e., no cycles of length $\leq 6$), the mixing time of the Glauber dynamics is $O(n\log{n})$ when $\lambda<\lambda_c(\Delta)$. Our work complements that of Weitz, which applies for small constant $\Delta$, whereas our work applies for all $\Delta$ at least a sufficiently large constant $\Delta_0$. (This includes $\Delta$ depending on $n=|V|$.) Our proof utilizes loopy belief propagation (BP) which is a widely used algorithm for inference in graphical models. A novel aspect of our work is using the principal eigenvector for the BP operator to design a distance function which contracts in expectation for pairs of states that behave like the BP fixed point. We also prove that the Glauber dynamics behaves locally like loopy BP. As a byproduct we obtain that the Glauber dynamics, after a short burn-in period, converges close to the BP fixed point, and this implies that the fixed point of loopy BP is a close approximation to the Gibbs distribution. Using these connections we establish that loopy BP quickly converges to the Gibbs distribution when the girth $\geq 6$ and $\lambda<\lambda_c(\Delta)$.

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.

We study the problem of approximately counting matchings in hypergraphs of bounded maximum degree and maximum size of hyperedges. With an activity parameter lambda, each matching M is assigned a weight lambda^{|M|}. The counting problem is formulated as computing a partition function that gives the sum of the weights of all matchings in a hypergraph. This problem unifies two extensively studied statistical physics models in approximate counting: the hardcore model (graph independent sets) and the monomer-dimer model (graph matchings). For this model, the critical activity lambda_c= (d^d)/(k (d-1)^{d+1}) is the threshold for the uniqueness of Gibbs measures on the infinite (d+1)-uniform (k+1)-regular hypertree. Consider hypergraphs of maximum degree at most k+1 and maximum size of hyperedges at most d+1. We show that when lambda < lambda_c, there is an FPTAS for computing the partition function; and when lambda = lambda_c, there is a PTAS for computing the log-partition function. These algorithms are based on the decay of correlation (strong spatial mixing) property of Gibbs distributions. When lambda > 2lambda_c, there is no PRAS for the partition function or the log-partition function unless NP=RP. Towards obtaining a sharp transition of computational complexity of approximate counting, we study the local convergence from a sequence of finite hypergraphs to the infinite lattice with specified symmetry. We show a surprising connection between the local convergence and the reversibility of a natural random walk. This leads us to a barrier for the hardness result: The non-uniqueness of infinite Gibbs measure is not realizable by any finite gadgets.

We study the problem of sampling almost uniform proper q-colorings in sparse Erdos-Renyi random graphs G(n,d/n), a research initiated by Dyer, Flaxman, Frieze and Vigoda [Dyer et al., RANDOM STRUCT ALGOR, 2006]. We obtain a fully polynomial time almost uniform sampler (FPAUS) for the problem provided q>3d+4, improving the current best bound q>5.5d [Efthymiou, SODA, 2014]. Our sampling algorithm works for more generalized models and broader family of sparse graphs. It is an efficient sampler (in the same sense of FPAUS) for anti-ferromagnetic Potts model with activity 0<=b<1 on G(n,d/n) provided q>3(1-b)d+4. We further identify a family of sparse graphs to which all these results can be extended. This family of graphs is characterized by the notion of contraction function, which is a new measure of the average degree in graphs.

We study the hard-core (gas) model defined on independent sets of an input graph where the independent sets are weighted by a parameter (aka fugacity) λ > 0. For constant Δ, previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree Δ when λc(Δ). Sly (2010) showed that there is no FPRAS, unless NP=RP, when λ > λc(Δ). The threshold λc(Δ) is the critical point for the statistical physics phase transition for uniqueness/non-uniqueness on the infinite Δ-regular tree. The running time of Weitz's algorithm is exponential in log Δ. Here we present an FPRAS for the partition function whose running time is O* (n2). We analyze the simple single-site Markov chain known as the Glauber dynamics for sampling from the associated Gibbs distribution. We prove there exists a constant Δ0such that for all graphs with maximum degree Δ > Δ0and girth > 7 (i.e., no cycles of length ≤ 6), the mixing time of the Glauber dynamics is O(nlog n) when λc(Δ). Our work complements that of Weitz which applies for small constant Δ whereas our work applies for all Δ at least a sufficiently large constant Δ0(this includes Δ depending on n = IVI). Our proof utilizes loopy BP (belief propagation) which is a widely-used algorithm for inference in graphical models. A novel aspect of our work is using the principal eigenvector for the BP operator to design a distance function which contracts in expectation for pairs of states that behave like the BP fixed point. We also prove that the Glauber dynamics behaves locally like loopy BP. As a byproduct we obtain that the Glauber dynamics, after a short burn-in period, converges close to the BP fixed point, and this implies that the fixed point of loopy BP is a close approximation to the Gibbs distribution. Using these connections we establish that loopy BP quickly converges to the Gibbs distribution when the girth ≥ 6 and λc(Δ).

We prove an Omega(d/log(sw/nd)) lower bound for the average-case cell-probe complexity of deterministic or Las Vegas randomized algorithms solving approximate near-neighbor (ANN) problem in ddimensional Hamming space in the cell-probe model with w-bit cells, using a table of size s. This lower bound matches the highest known worst-case cell-probe lower bounds for any static data structure problems. This average-case cell-probe lower bound is proved in a general framework which relates the cell-probe complexity of ANN to isoperimetric inequalities in the underlying metric space. A tighter connection between ANN lower bounds and isoperimetric inequalities is established by a stronger richness lemma proved by cell-sampling techniques.

We study the problem of approximate nearest neighbor search in $d$-dimensional Hamming space {0,1}d. We study the complexity of the problem in the famous cell-probe model, a classic model for data structures. We consider algorithms in the cell-probe model with limited adaptivity, where the algorithm makes k rounds of parallel accesses to the data structure for a given k. For any k ≥ 1, we give a simple randomized algorithm solving the approximate nearest neighbor search using k rounds of parallel memory accesses, with O(k(log d)1/k) accesses in total. We also give a more sophisticated randomized algorithm using O(k+(1/k log d)O(1/k)) memory accesses in k rounds for large enough k. Both algorithms use data structures of size polynomial in n, the number of points in the database. We prove an Ω(1/k(log d)1/k) lower bound for the total number of memory accesses required by any randomized algorithm solving the approximate nearest neighbor search within k ≤ (log log d)/(2 log log log d) rounds of parallel memory accesses on any data structures of polynomial size. This lower bound shows that our first algorithm is asymptotically optimal for any constant round k. And our second algorithm approaches the asymptotically optimal tradeoff between rounds and memory accesses, in a sense that the lower bound of memory accesses for any k1 rounds can be matched by the algorithm within k2=O(k1) rounds. In the extreme, for some large enough k=Θ((log log d)/(log log log d)), our second algorithm matches the Θ((log log d)/(log log log d)) tight bound for fully adaptive algorithms for approximate nearest neighbor search due to Chakrabarti and Regev.

We study the problem of deterministic approximate counting of matchings and independent sets in graphs of bounded connective constant. More generally, we consider the problem of evaluating the partition functions of the monomer-dimer model (which is defined as a weighted sum over all matchings where each matching is given a weight γ|V| –2|M| in terms of a fixed parameter γ called the monomer activity) and the hard core model (which is defined as a weighted sum over all independent sets where an independent set I is given a weight γ|I| in terms of a fixed parameter γ called the vertex activity). The connective constant is a natural measure of the average degree of a graph which has been studied extensively in combinatorics and mathematical physics, and can be bounded by a constant even for certain unbounded degree graphs such as those sampled from the sparse Erdös-Rényi model (n, d/n). Our main technical contribution is to prove the best possible rates of decay of correlations in the natural probability distributions induced by both the hard core model and the monomer-dimer model in graphs with a given bound on the connective constant. These results on decay of correlations are obtained using a new framework based on the so-called message approach that has been extensively used recently to prove such results for bounded degree graphs. We then use these optimal decay of correlations results to obtain FPTASs for the two problems on graphs of bounded connective constant. In particular, for the monomer-dimer model, we give a deterministic FPTAS for the partition function on all graphs of bounded connective constant for any given value of the monomer activity. The best previously known deterministic algorithm was due to Bayati, Gamarnik, Katz, Nair and Tetali [STOC 2007], and gave the same runtime guarantees as our results but only for the case of bounded degree graphs. For the hard core model, we give an FPTAS for graphs of connective constant Δ whenever the vertex activity λ < λc(Δ), where ; this result is optimal in the sense that an FPTAS for any λ > λc(Δ) would imply that NP=RP [Sly, FOCS 2010]. The previous best known result in this direction was a recent paper by a subset of the current authors [FOCS 2013], where the result was established under the suboptimal condition λ < λc(Δ + 1). Our techniques also allow us to improve upon known bounds for decay of correlations for the hard core model on various regular lattices, including those obtained by Restrepo, Shin, Vigoda and Tetali [FOCS 11] for the special case of ℤ2 using sophisticated numerically intensive methods tailored to that special case.

We apply several state-of-the-art techniques developed in recent advances of counting algorithms and statistical physics to study the spatial mixing property of the two-dimensional codes arising from local hard (independent set) constraints, including: hard-square, hard-hexagon, read/write isolated memory (RWIM), and non-attacking kings (NAK). For these constraints, the strong spatial mixing would imply the existence of polynomial-time approximation scheme (PTAS) for computing the capacity. The existence of strong spatial mixing and a PTAS were previously known for the hard-square constraint. We show the existence of strong spatial mixing for hard-hexagon and RWIM constraints, and consequently we give PTAS for computing the capacities of these codes. We also show evidence that the strong spatial mixing may not hold for the NAK constraint.

Consider a wireless network in which selfish users compete with each other for usage of spectrum. We view this competition as a spatial spectrum access game. There are two fundamental questions regarding this game: how to converge to the optimal Nash equilibrium, and how to converge fast. To answer these two questions, we apply a technique called Belief Propagation to design algorithms for users in this game, which can guarantee fast convergence to an optimal or nearly optimal pure strategy Nash equilibrium. Specifically, when the interference graph is an undirected tree or a directed acyclic graph, our algorithms can find the optimal Nash equilibrium in linear time. For general undirected interference graph, our algorithm converges fast as long as the game is potential (which is the case for many typical scenarios). For some other typical spatial spectrum access games, our algorithms can provide a good approximation to the optimal Nash equilibrium.

The hard core model in statistical physics is a probability distribution on independent sets in a graph in which the weight of any independent set I is proportional to λ|I|, where λ > 0 is the vertex activity. We show that there is an intimate connection between the connective constant of a graph and the phenomenon of strong spatial mixing (decay of correlations) for the hard core model; specifically, we prove that the hard core model with vertex activity λc(Δ+1) exhibits strong spatial mixing on any graph of connective constant Δ, irrespective of its maximum degree, and hence derive an FPTAS for the partition function of the hard core model on such graphs. Here λc(d) ··= dd/(d-1)d+1is the critical activity for the uniqueness of the Gibbs measure of the hard core model on the infinite d-ary tree. As an application, we show that the partition function can be efficiently approximated with high probability on graphs drawn from the random graph model G (n, d/n) for all λ <; e/d, even though the maximum degree of such graphs is unbounded with high probability. We also improve upon Weitz's bounds for strong spatial mixing on bounded degree graphs [30] by providing a computationally simple method which uses known estimates of the connective constant of a lattice to obtain bounds on the vertex activities λ for which the hard core model on the lattice exhibits strong spatial mixing. Using this framework, we improve upon these bounds for several lattices including the Cartesian lattice in dimensions 3 and higher. Our techniques also allow us to relate the threshold for the uniqueness of the Gibbs measure on a general tree to its branching factor [15].

We give a complete characterization of the two-state anti-ferromagnetic spin systems which exhibit strong spatial mixing on general graphs. We show that a two-state anti-ferromagnetic spin system exhibits strong spatial mixing on all graphs of maximum degree at most Δ if and only if the system has a unique Gibbs measure on infinite regular trees of degree up to Δ, where Δ can be either bounded or unbounded. As a consequence, there exists an FPTAS for the partition function of a two-state anti-ferromagnetic spin system on graphs of maximum degree at most Δ when the uniqueness condition is satisfied on infinite regular trees of degree up to Δ. In particular, an FPTAS exists for arbitrary graphs if the uniqueness is satisfied on all infinite regular trees. This covers as special cases all previous algorithmic results for two-state anti-ferromagnetic systems on general-structure graphs. Combining with the FPRAS for two-state ferromagnetic spin systems of Jerrum-Sinclair and Goldberg-Jerrum-Paterson, and the very recent hardness results of Sly-Sun and independently of Galanis-Štefankovič-Vigoda, this gives a complete classification, except at the phase transition boundary, of the approximability of all two-state spin systems, on either degree-bounded families of graphs or family of all graphs.

We show for a broad class of counting problems, correlation decay (strong spatial mixing) implies FPTAS on planar graphs. The framework for the counting problems considered by us is the Holant problems with arbitrary constant-size domain and symmetric constraint functions. We define a notion of regularity on the constraint functions, which covers a wide range of natural and important counting problems, including all multistate spin systems, counting graph homomorphisms, counting weighted matchings or perfect matchings, and all counting CSPs and Holant problems with symmetric constraint functions of constant arity. The core of our algorithm is a fixed-parameter tractable algorithm which computes the exact values of the Holant problems with regular constraint functions on graphs of bounded treewidth. By utilizing the locally tree-like property of apex-minor-free families of graphs, the parameterized exact algorithm implies an FPTAS for the Holant problem on these graph families whenever the Gibbs measure defined by the problem exhibits strong spatial mixing. We further extend the recursive coupling technique to establish the strong spatial mixing on Holant problems. As consequences, we have new deterministic approximation algorithms on planar graphs for several counting problems.

Chunked codes are a variation of random linear network codes with low computational complexities. In chunked codes, the packets in a file are grouped into small (non-overlapped or overlapped) chunks, and random linear encoding operations are performed within each chunk. Previous studies show that when the chunk size is lower bounded by some increasing function of the file length, chunked codes asymptotically achieve the min-cut capacity. However, in most real applications, the chunk size is required to be a small constant due to the computational constraints of network devices. In this case, it remains unknown which rates can be achieved by chunked codes. In this paper, we address the analysis and design of chunked codes with fixed constant chunk sizes. We first highlight the importance of precoding for chunked codes to achieve constant rates, and then present an analysis of non-overlapped chunked (NOC) codes with precoding. We further introduce a new class of chunked codes, called EOC codes, which are based on expander graphs to form overlapped chunks. Numerical and simulation results show that EOC codes achieve significantly higher rates than NOC codes, and also outperform other state-of-the-art overlapped chunked codes.

We give the first deterministic fully polynomial-time approximation scheme (FPTAS) for computing the partition function of a two-state spin system on an arbitrary graph, when the parameters of the system satisfy the uniqueness condition on infinite regular trees. This condition is of physical significance and is believed to be the right boundary between approximable and inapproximable. The FPTAS is based on the correlation decay technique introduced by Bandyopadhyay and Gamarnik [1] and Weitz [61]. The classic correlation decay is defined with respect to graph distance. Although this definition has natural physical meanings, it does not directly support an FPTAS for systems on arbitrary graphs, because for graphs with unbounded degrees, the local computation that provides a desirable precision by correlation decay may take super-polynomial time. We introduce a notion of computationally efficient correlation decay, in which the correlation decay is measured in a refined metric instead of graph distance. We use a potential method to analyze the amortized behavior of this correlation decay and establish a correlation decay that guarantees an inverse-polynomial precision by polynomial-time local computation. This gives us an FPTAS for spin systems on arbitrary graphs. This new notion of correlation decay properly reflects the algorithmic aspect of the spin systems, and may be used for designing FPTAS for other counting problems.

We consider the problem of minimizing contention in static dictionary data structures, where the contention on each cell is measured by the expected number of probes to that cell given an input that is chosen from a distribution that is not known to the query algorithm (but that may be known when the data structure is built). When all positive queries are equally probable, and similarly all negative queries are equally probable, we show that it is possible to construct a data structure using linear space s, a constant number of queries, and with contention O(1/s) on each cell, corresponding to a nearly-flat load distribution. All of these quantities are asymptotically optimal. For arbitrary query distributions, the lack of knowledge of the query distribution by the query algorithm prevents perfect load leveling in this case: we present a lower bound, based on VC-dimension, that shows that for a wide range of data structure problems, achieving contention even within a polylogarithmic factor of optimal requires a cell-probe complexity of Ω(log log n).

In recent years Google’s MapReduce has emerged as a leading large-scale data processing architecture. Adopted by companies such as Amazon, Facebook, Google, IBM and Yahoo! in daily use, and more recently put in use by several universities, it allows parallel processing of huge volumes of data over cluster of machines. Hadoop is a free Java implementation of MapReduce. In Hadoop, files are split into blocks and replicated and spread over all servers in a network. Each job is also split into many small pieces called tasks. Several tasks are processed on a single server, and a job is not completed until all the assigned tasks are finished. A crucial factor that affects the completion time of a job is the particular assignment of tasks to servers. Given a placement of the input data over servers, one wishes to find the assignment that minimizes the total completion time. In this paper, an idealized Hadoop model is proposed to investigate the Hadoop task assignment problem. It is shown that there is no feasible algorithm to find the optimal Hadoop task assignment unless P = NP. Assignments that are computed by the round robin algorithm inspired by the current Hadoop scheduler are shown to deviate from optimum by a multiplicative factor in the worst case. A flow-based algorithm is presented that computes assignments that are optimal to within an additive constant.

An asynchronous algorithm is described for rapidly constructing an overlay network in a peer-to-peer system where all nodes can in principle communicate with each other directly through an underlying network, but each participating node initially has pointers to only a handful of other participants. The output of the mechanism is a linked list of all participants sorted by their identifiers, which can be used as a foundation for building various linear overlay networks such as Chord or skip graphs. Assuming the initial pointer graph is weakly-connected with maximum degree d and the length of a node identifier is W, the mechanism constructs a binary search tree of nodes of depth O(W) in expected O(W log n) time using expected O((d+W)nlog n) messages of size O(W) each. Furthermore, the algorithm has low contention: at any time there are only O(d) undelivered messages for any given recipient. A lower bound of Ω(d + log n) is given for the running time of any procedure in a related synchronous model that yields a sorted list from a degree-d weakly-connected graph of n nodes. We conjecture that this lower bound is tight and could be attained by further improvements to our algorithms.