The hardcore model is one of the most classic and widely studied examples of undirected graphical models. Given a graph G, the hardcore model describes a Gibbs distribution of λ-weighted independent sets of G. In the last two decades, a beautiful computational phase transition has been established at a precise threshold λ_c(Δ) where Δ denotes the maximum degree, where the task of sampling independent sets transitions from polynomial-time solvable to computationally intractable. We study the critical hardcore model where λ = λ_c(Δ) and show that the Glauber dynamics, a simple yet popular Markov chain algorithm, mixes in Õ(n^{7.44 + O(1/Δ)}) time on any n-vertex graph of maximum degree Δ ≥ 3, significantly improving the previous upper bound Õ(n^{12.88 + O(1/Δ)}) by the recent work [Chen et al., 2024]. The core property we establish in this work is that the critical hardcore model is O(√n)-spectrally independent, improving the trivial bound of n and matching the critical behavior of the Ising model. Our proof approach utilizes an online decision-making framework to study a site percolation model on the infinite (Δ-1)-ary tree, which can be interesting by itself.

The Metropolis process (MP) and Simulated Annealing (SA) are stochastic local search heuristics that are often used in solving combinatorial optimization problems. Despite significant interest, there are very few theoretical results regarding the quality of approximation obtained by MP and SA (with polynomially many iterations) for NP-hard optimization problems. We provide rigorous lower bounds for MP and SA with respect to the classical maximum independent set problem when the algorithms are initialized from the empty set. We establish the existence of a family of graphs for which both MP and SA fail to find approximate solutions in polynomial time. More specifically, we show that for any $\varepsilon \in (0,1)$ there are $n$-vertex graphs for which the probability SA (when limited to polynomially many iterations) will approximate the optimal solution within ratio $Ω\left(\frac{1}{n^{1-\varepsilon}}\right)$ is exponentially small. Our lower bounds extend to graphs of constant average degree $d$, illustrating the failure of MP to achieve an approximation ratio of $Ω\left(\frac{\log (d)}{d}\right)$ in polynomial time. In some cases, our impossibility results also go beyond Simulated Annealing and apply even when the temperature is chosen adaptively. Finally, we prove time lower bounds when the inputs to these algorithms are bipartite graphs, and even trees, which are known to admit polynomial-time algorithms for the independent set problem.

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 study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution \(\mu\) , an \(\varepsilon \gt 0\) , and access to sampling oracle(s) for a hidden distribution \(\pi\) , the goal in identity testing is to distinguish whether the two distributions \(\mu\) and \(\pi\) are identical or are at least \(\varepsilon\) -far apart. When there is only access to full samples from the hidden distribution \(\pi\) , it is known that exponentially many samples (in the dimension) may be needed for identity testing, and hence previous works have studied identity testing with additional access to various “conditional” sampling oracles. We consider a significantly weaker conditional sampling oracle, which we call the \(\mathsf{Coordinate\ Oracle}\) , and provide a computational and statistical characterization of the identity testing problem in this new model. We prove that if an analytic property known as approximate tensorization of entropy holds for an \(n\) -dimensional visible distribution \(\mu\) , then there is an efficient identity testing algorithm for any hidden distribution \(\pi\) using \(\widetilde{O}(n/\varepsilon)\) queries to the \(\mathsf{Coordinate\ Oracle}\) . Approximate tensorization of entropy is a pertinent condition as recent works have established it for a large class of high-dimensional distributions. We also prove a computational phase transition: For a well-studied class of \(n\) -dimensional distributions, specifically sparse anti-ferromagnetic Ising models over \(\{+1,-1\}^{n}\) , we show that in the regime where approximate tensorization of entropy fails, there is no efficient identity testing algorithm unless \(\mathsf{RP}=\mathsf{NP}\) . We complement our results with a matching \(\Omega(n/\varepsilon)\) statistical lower bound for the sample complexity of identity testing in the \(\mathsf{Coordinate\ Oracle}\) model.

Given a complex high-dimensional distribution over {± 1}ⁿ, what is the best way to increase the expected number of +1’s by controlling the values of only a small number of variables? Such a problem is known as influence maximization and has been widely studied in social networks, biology, and computer science. In this paper, we consider influence maximization on the Ising model which is a prototypical example of undirected graphical models and has wide applications in many real-world problems. We establish a sharp computational phase transition for influence maximization on sparse Ising models under a bounded budget: In the high-temperature regime, we give a linear-time algorithm for finding a small subset of variables and their values which achieve nearly optimal influence; In the low-temperature regime, we show that the influence maximization problem cannot be solved in polynomial time under commonly-believed complexity assumption. The critical temperature coincides with the tree uniqueness/non-uniqueness threshold for Ising models which is also a critical point for other computational problems including approximate sampling and counting.

We present a simple combinatorial framework for establishing approximate tensorization of variance and entropy in the setting of spin systems (a.k.a. undirected graphical models) based on balanced separators of the underlying graph. Such approximate tensorization results immediately imply as corollaries many important structural properties of the associated Gibbs distribution, in particular rapid mixing of the Glauber dynamics for sampling. We prove approximate tensorization by recursively establishing block factorization of variance and entropy with a small balanced separator of the graph. Our approach goes beyond the classical canonical path method for variance and the recent spectral independence approach, and allows us to obtain new rapid mixing results. As applications of our approach, we show that:

For an integer b ≥ 1, a b-matching (resp. b-edge cover) of a graph G = (V, E) is a subset S ⊆ E of edges such that every vertex is incident with at most (resp. at least) b edges from S. We prove that for any b ≥ 1 the simple Glauber dynamics for sampling (weighted) b-matchings and b-edge covers mixes in O(n log n) time on all n-vertex bounded-degree graphs. This significantly improves upon previous results which have worse running time and only work for b-matchings with b ≤ 7 and for b-edge covers with b ≤ 2.

Abstract. We give a nearly linear-time algorithm to approximately sample satisfying assignments in the random [Formula: see text]-SAT model when the density of the formula scales exponentially with [Formula: see text]. The best previously known sampling algorithm for the random [Formula: see text]-SAT model applies when the density [Formula: see text] of the formula is less than [Formula: see text] and runs in time [Formula: see text] [Galanis et al., SIAM J. Comput., 50 (2021), pp. 1701–1738]. Here [Formula: see text] is the number of variables and [Formula: see text] is the number of clauses. Our algorithm achieves a significantly faster running time of [Formula: see text] and samples satisfying assignments up to density [Formula: see text]. The main challenge in our setting is the presence of many variables with unbounded degree, which causes significant correlations within the formula and impedes the application of relevant Markov chain methods from the bounded-degree setting [Feng et al., J. ACM, 68 (2021) 40; Jain, Pham, and Vuong, On the Sampling Lovász Local Lemma for Atomic Constraint Satisfaction Problems, 2021]. Our main technical contribution is a [Formula: see text] bound of the sum of influences in the [Formula: see text]-SAT model which turns out to be robust against the presence of high-degree variables. This allows us to apply the spectral independence framework and obtain fast mixing results of a uniform-block Glauber dynamics on a carefully selected subset of the variables. The final key ingredient in our method is to take advantage of the sparsity of logarithmic-sized connected sets and the expansion properties of the random formula, and establish relevant connectivity properties of the set of satisfying assignments that enable the fast simulation of this Glauber dynamics. Our results also allow us to conclude that, with high probability, a random [Formula: see text]-CNF formula with density at most [Formula: see text] has a giant component of solutions that are connected in a graph where solutions are adjacent if they have Hamming distance [Formula: see text]. We are also able to deduce looseness results for random [Formula: see text]-CNFs in the same regime.

We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution $\mu$, an $\varepsilon>0$, and access to sampling oracle(s) for a hidden distribution $\pi$, the goal in identity testing is to distinguish whether the two distributions $\mu$ and $\pi$ are identical or are at least $\varepsilon$-far apart. When there is only access to full samples from the hidden distribution $\pi$, it is known that exponentially many samples (in the dimension) may be needed for identity testing, and hence previous works have studied identity testing with additional access to various “conditional” sampling oracles. We consider a significantly weaker conditional sampling oracle, which we call the Coordinate Oracle, and provide a computational and statistical characterization of the identity testing problem in this new model.We prove that if an analytic property known as approximate tensorization of entropy holds for an $n$-dimensional visible distribution $\mu$, then there is an efficient identity testing algorithm for any hidden distribution $\pi$ using $\widetilde{O}(n/\varepsilon)$ queries to the Coordinate Oracle. Approximate tensorization of entropy is a pertinent condition as recent works have established it for a large class of high-dimensional distributions. We also prove a computational phase transition: for a well-studied class of $n$-dimensional distributions, specifically sparse antiferromagnetic Ising models over $\{+1,-1\}^n$, we show that in the regime where approximate tensorization of entropy fails, there is no efficient identity testing algorithm unless RP=NP. We complement our results with a matching $\Omega(n/\varepsilon)$ statistical lower bound for the sample complexity of identity testing in the $\coorora$ model.

Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical computer science. A longstanding conjecture is that the uniform distribution on proper q-colorings on a $\Delta$ regular tree exhibits SSM whenever $q \geq \Delta+1$. Moreover, it is widely believed that as long as SSM holds on bounded-degree trees with q colors, one would obtain an efficient sampler for q-colorings on all bounded-degree graphs via simple Markov chain algorithms. It is surprising that such a basic question is still open, even on trees, but then again it also highlights how much we still have to learn about random colorings. In this paper, we show the following: (1)For any $\Delta \geq 3$, SSM holds for random q-colorings on trees of maximum degree $\Delta$ whenever $q \geq \Delta+3$. Thus we almost fully resolve the aforementioned conjecture. Our result substantially improves upon the previously best bound which requires $q \geq 1.59 \Delta+\gamma^{*}$ for an absolute constant $\gamma^{*}\gt0$.(2)For any $\Delta \geq 3$ and $g=\Omega_{\Delta}(1)$, we establish optimal mixing of the Glauber dynamics for q-colorings on graphs of maximum degree $\Delta$ and girth g whenever $q \geq \Delta+3$. Our approach is based on a new general reduction from spectral independence on large-girth graphs to SSM on trees that is of independent interest. Using the same techniques, we also prove near-optimal bounds on weak spatial mixing (WSM), a closely-related notion to SSM, for the antiferromagnetic Potts model on trees.

We take an algorithmic approach to studying the solution space geometry of relatively sparse random and bounded degree k-CNFs for large k. In the course of doing so, we establish that with high probability, a random k-CNF Φ with n variables and clause density α = m/n ≲ 2k/6 has a giant component of solutions that are connected in a graph where solutions are adjacent if they have Hamming distance Ok(log n) and that a similar result holds for bounded degree k-CNFs at similar densities. We are also able to deduce looseness results for random and bounded degree k-CNFs in a similar regime. Although our main motivation was understanding the geometry of the solution space, our methods have algorithmic implications. Towards that end, we construct an idealized block dynamics that samples solutions from a random k-CNF Φ with density α = m/n ≲ 2k/52. We show this Markov chain can with high probability be implemented in polynomial time and by leveraging spectral independence, we also observe that it mixes relatively fast, giving a polynomial time algorithm to with high probability sample a uniformly random solution to a random k-CNF. Our work suggests that the natural route to pinning down when a giant component exists is to develop sharper algorithms for sampling solutions to random k-CNFs.

A seminal work of Jerrum (1992) showed that large cliques elude the Metropolis process. More specifically, Jerrum showed that the Metropolis algorithm cannot find a clique of size k = Θ(nα) for α ∈ (0,1/2), which is planted in the Erdős-Rényi random graph G(n, 1/2), in polynomial time. Information theoretically it is possible to find such planted cliques as soon as k ≥ (2 + ε) log n. Since the work of Jerrum, the computational problem of finding a planted clique in G(n, 1/2) was studied extensively and many polynomial time algorithms were shown to find the planted clique if it is of size , while no polynomial-time algorithm is known to work when . The computational problem of finding a planted clique of size is now widely considered as a foundational problem in the study of computational-statistical gaps. Notably, the first evidence of the problem's algorithmic hardness is commonly attributed to the result of Jerrum from 1992.

Abstract. For general antiferromagnetic 2-spin systems, including the hardcore model on weighted independent sets and the antiferromagnetic Ising model, there is an [Formula: see text] for the partition function on graphs of maximum degree [Formula: see text] when the infinite regular tree lies in the uniqueness region by Li, Lu, and Yin [ Correlation Decay up to Uniqueness in Spin Systems, preprint, https://arxiv.org/abs/1111.7064 , 2021]. Moreover, in the tree nonuniqueness region, Sly in [ Computational transition at the uniqueness threshold, in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 287–296] showed that there is no [Formula: see text] to estimate the partition function unless [Formula: see text]. The algorithmic results follow from the correlation decay approach due to Weitz [ Counting independent sets up to the tree threshold, in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 140–149] or the polynomial interpolation approach developed by Barvinok [ Combinatorics and Complexity of Partition Functions, Springer, 2016]. However, the running time is only polynomial for constant [Formula: see text]. For the hardcore model, recent work of Anari, Liu, and Oveis Gharan [ Spectral independence in high-dimensional expanders and applications to the hardcore model, in Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science, 2020, pp. 1319–1330] establishes rapid mixing of the simple single-site Markov chain, known as the Glauber dynamics, in the tree uniqueness region. Our work simplifies their analysis of the Glauber dynamics by considering the total pairwise influence of a fixed vertex [Formula: see text] on other vertices, as opposed to the total influence of other vertices on [Formula: see text], thereby extending their work to all 2-spin models and improving the mixing time. More important, our proof ties together the three disparate algorithmic approaches: we show that contraction of the so-called tree recursions with a suitable potential function, which is the primary technique for establishing efficiency of Weitz’s correlation decay approach and Barvinok’s polynomial interpolation approach, also establishes rapid mixing of the Glauber dynamics. We emphasize that this connection holds for all 2-spin models (both antiferromagnetic and ferromagnetic), and existing proofs for the correlation decay and polynomial interpolation approaches immediately imply rapid mixing of the Glauber dynamics. Our proof utilizes the fact that the graph partition function is a divisor of the partition function for Weitz’s self-avoiding walk tree. This fact leads to new tools for the analysis of the influence of vertices and may be of independent interest for the study of complex zeros.

For general spin systems, we prove that a contractive coupling for an arbitrary local Markov chain implies optimal bounds on the mixing time and the modified log-Sobolev constant for a large class of Markov chains including the Glauber dynamics, arbitrary heat-bath block dynamics, and the Swendsen-Wang dynamics. This reveals a novel connection between probabilistic techniques for bounding the convergence to stationarity and analytic tools for analyzing the decay of relative entropy. As a corollary of our general results, we obtain O(n log n) mixing time and Ω(1/n) modified log-Sobolev constant of the Glauber dynamics for sampling random q-colorings of an n-vertex graph with constant maximum degree Δ when q > (11/6–∊0)Δ for some fixed ∊0 > 0. We also obtain O(log n) mixing time and Ω(1) modified log-Sobolev constant of the Swendsen-Wang dynamics for the ferromagnetic Ising model on an n-vertex graph of constant maximum degree when the parameters of the system lie in the tree uniqueness region. At the heart of our results are new techniques for establishing spectral independence of the spin system and block factorization of the relative entropy. On one hand we prove that a contractive coupling of any local Markov chain implies spectral independence of the Gibbs distribution. On the other hand we show that spectral independence implies factorization of entropy for arbitrary blocks, establishing optimal bounds on the modified log-Sobolev constant of the corresponding block dynamics.

We give an FPRAS for counting q-colorings for even on almost every Δ-regular bipartite graph. This improves significantly upon the previous best bound of by Jenssen, Keevash, and Perkins (SODA'19). Analogously, for the hard-core model on independentsets weighted by λ > 0, we present an FPRAS for estimating the partition function when , which improves upon previous results by an Ω(log Δ) factor. Our results for the colorings and hard-core models follow from a general result that applies to arbitrary spin systems. Our main contribution is to show how to elevate probabilistic/analytic bounds on the marginal probabilities for the typical structure of phases on random bipartite regular graphs into efficient algorithms, using the polymer method. We further show evidence that our results for colorings and independent sets are within a constant factor of best possible using current polymer-method approaches.

The Swendsen-Wang algorithm is a sophisticated, widely-used Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. This chain has proved difficult to analyze, due in part to the global nature of its updates. We present optimal bounds on the convergence rate of the Swendsen-Wang algorithm for the complete d-ary tree. Our bounds extend to the non-uniqueness region and apply to all boundary conditions. We show that the spatial mixing conditions known as Variance Mixing and Entropy Mixing, introduced in the study of local Markov chains by Martinelli et al. (2003), imply Ω(1) spectral gap and O(log n) mixing time, respectively, for the Swendsen-Wang dynamics on the d-ary tree. We also show that these bounds are asymptotically optimal. As a consequence, we establish Θ(log n) mixing for the Swendsen-Wang dynamics for all boundary conditions throughout the tree uniqueness region; in fact, our bounds hold beyond the uniqueness threshold for the Ising model, and for the q-state Potts model when q is small with respect to d. Our proofs feature a novel spectral view of the Variance Mixing condition inspired by several recent rapid mixing results on high-dimensional expanders and utilize recent work on block factorization of entropy under spatial mixing conditions.

This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition function is nonzero in a region around a real point$\lambda$then spectral independence holds at$\lambda$. As a consequence, for Holant-type problems (e.g., spin systems) on bounded-degree graphs, we obtain optimal$O(n\ \text{log}\ n)$mixing time bounds for the single-site update Markov chain known as the Glauber dynamics. Our result significantly improves the running time guarantees obtained via the polynomial interpolation method of Barvi-nok (2017), refined by Patel and Regts (2017). There are a variety of applications of our results. In this paper, we focus on Holant-type (i.e., edge-coloring) problems, including weighted edge covers and weighted even subgraphs. For the weighted edge cover problem (and several natural generalizations) we obtain an$O$($n$log n) sampling algorithm on bounded-degree graphs. The even subgraphs problem corresponds to the high-temperature expansion of the ferromagnetic Ising model. We obtain an$O$($n$log n) sampling algorithm for the ferromagnetic Ising model with a nonzero external field on bounded-degree graphs, which improves upon the classical result of Jerrum and Sinclair (1993) for this class of graphs. We obtain further applications to antiferromagnetic two-spin models on line graphs, weighted graph homomorphisms, tensor networks, and more.

The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber dynamics for the hard-core model defined on weighted independent sets. We develop the spectral independence approach for colorings, and obtain new algorithmic results for the corresponding counting/sampling problems. Let α∗ ≈ 1.763 denote the solution to exp(1/x) = x and let α > α∗. We prove that, for any triangle-free graph G = (V, E) with maximum degree Δ, for all q ≥ αΔ + 1, the mixing time of the Glauber dynamics for q-colorings is polynomial in n = |V|, with the exponent of the polynomial independent of Δ and q. In comparison, previous approximate counting results for colorings held for a similar range of q (asymptotically in Δ) but with larger girth requirement or with a running time where the polynomial exponent depended on Δ and q (exponentially). One further feature of using the spectral independence approach to study colorings is that it avoids many of the technical complications in previous approaches caused by coupling arguments or by passing to the complex plane; the key improvement on the running time is based on relatively simple combinatorial arguments which are then translated into spectral bounds.

We prove an optimal mixing time bound for the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an improved version of the spectral independence approach of Anari et al. (2020) and shows O(nlogn) mixing time on any n-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. As an application of our results, for the hard-core model on independent sets weighted by a fugacity λ, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree Δ when λ<λc(Δ) where λc(Δ) is the critical point for the uniqueness/non-uniqueness phase transition on the Δ-regular tree. More generally, for any antiferromagnetic 2-spin system we prove O(nlogn) mixing time of the Glauber dynamics on any bounded degree graph in the corresponding tree uniqueness region. Our results apply more broadly; for example, we also obtain O(nlogn) mixing for q-colorings of triangle-free graphs of maximum degree Δ when the number of colors satisfies q > α Δ where α ≈ 1.763, and O(mlogn) mixing for generating random matchings of any graph with bounded degree and m edges.

We study the identity testing problem for restricted Boltzmann machines (RBMs), and more generally, for undirected graphical models. In this problem, given sample access to the Gibbs distribution corresponding to an unknown or hidden model $M^*$ and given an explicit model $M$, the goal is to distinguish if either $M = M^*$ or if the models are (statistically) far apart. We establish the computational hardness of identity testing for RBMs (i.e., mixed Ising models on bipartite graphs), even when there are no latent variables or an external field. Specifically, we show that unless $RP=NP$, there is no polynomial-time identity testing algorithm for RBMs when $\beta d=\omega(\log{n})$, where $d$ is the maximum degree of the visible graph and $\beta$ is the largest edge weight (in absolute value); when $\beta d =O(\log{n})$ there is an efficient identity testing algorithm that utilizes the structure learning algorithm of Klivans and Meka (2017). We prove similar lower bounds for purely ferromagnetic RBMs with inconsistent external fields and for the ferromagnetic Potts model. To prove our results, we introduce a novel methodology to reduce the corresponding approximate counting problem to testing utilizing the phase transition exhibited by these models.

We study identity testing for restricted Boltzmann machines (RBMs), and more generally for undirected graphical models. Given sample access to the Gibbs distribution corresponding to an unknown or hidden model $M^*$ and given an explicit model $M$, can we distinguish if either $M = M^*$ or if they are (statistically) far apart? Daskalakis et al. (2018) presented a polynomial-time algorithm for identity testing for the ferromagnetic (attractive) Ising model. In contrast, for the antiferromagnetic (repulsive) Ising model, Bezáková et al. (2019) proved that unless $RP=NP$ there is no identity testing algorithm when $\beta d=\omega(\log{n})$, where $d$ is the maximum degree of the visible graph and $\beta$ is the largest edge weight (in absolute value). We prove analogous hardness results for RBMs (i.e., mixed Ising models on bipartite graphs), even when there are no latent variables or an external field. Specifically, we show that if $RP\neq NP$, then when $\beta d=\omega(\log{n})$ there is no polynomial-time algorithm for identity testing for RBMs; when $\beta d =O(\log{n})$ there is an efficient identity testing algorithm that utilizes the structure learning algorithm of Klivans and Meka (2017). In addition, we prove similar lower bounds for purely ferromagnetic RBMs with inconsistent external fields, and for the ferromagnetic Potts model. Previous hardness results for identity testing of Bezáková et al. (2019) utilized the hardness of finding the maximum cuts, which corresponds to the ground states of the antiferromagnetic Ising model. Since RBMs are on bipartite graphs such an approach is not feasible. We instead introduce a novel methodology to reduce from the corresponding approximate counting problem and utilize the phase transition that is exhibited by RBMs and the mean-field Potts model. We believe that our method is general, and that it can be used to establish the hardness of identity testing for other spin systems.

For general antiferromagnetic 2-spin systems, including the hardcore model on weighted independent sets and the antiferromagnetic Ising model, there is an FPTAS for the partition function on graphs of maximum degree Δ when the infinite regular tree lies in the uniqueness region by Li et al. (2013). Moreover, in the tree non-uniqueness region, Sly (2010) showed that there is no FPRAS to estimate the partition function unless NP=RP. The algorithmic results follow from the correlation decay approach due to Weitz (2006) or the polynomial interpolation approach developed by Barvinok (2016). However the running time is only polynomial for constant Δ. For the hardcore model, recent work of Anari et al. (2020) establishes rapid mixing of the simple single-site Markov chain known as the Glauber dynamics in the tree uniqueness region. Our work simplifies their analysis of the Glauber dynamics by considering the total pairwise influence of a fixed vertex v on other vertices, as opposed to the total influence of other vertices on v, thereby extending their work to all 2-spin models and improving the mixing time. More importantly our proof ties together the three disparate algorithmic approaches: we show that contraction of the so-called tree recursions with a suitable potential function, which is the primary technique for establishing efficiency of Weitz's correlation decay approach and Barvinok's polynomial interpolation approach, also establishes rapid mixing of the Glauber dynamics. We emphasize that this connection holds for all 2-spin models (both antiferromagnetic and ferromagnetic), and existing proofs for the correlation decay or polynomial interpolation approach immediately imply rapid mixing of the Glauber dynamics. Our proof utilizes that the graph partition function is a divisor of the partition function for Weitz's self-avoiding walk tree. This fact leads to new tools for the analysis of the influence of vertices, and may be of independent interest for the study of complex zeros.

We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model $M$ and a sampling oracle for the distribution $\mu_{M^*}$ of an unknown model $M^*$, can we efficiently determine if the two models $M$ and $M^*$ are the same? We consider identity testing for both soft-constraint and hard-constraint systems. In particular, we prove hardness results in two prototypical cases, the Ising model and proper colorings, and explore whether identity testing is any easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalakis et al. (2018) presented a polynomial-time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a super-polynomial number of samples. Specifically, for $n$-vertex graphs of maximum degree $d$, we prove that if $|\beta| d = \omega(\log{n})$ (where $\beta$ is the inverse temperature parameter), then there is no polynomial running time identity testing algorithm unless $RP=NP$. In the hard-constraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of #BIS, the problem of (approximately) counting independent sets in bipartite graphs.

We study the following structure learning problem forH-colorings. For a fixed (and known) constraint graphHwithqcolors, given access to uniformly randomH-colorings of an unknown graphG=(V,E), how many samples are required to learn the edges of G? We give a characterization of the constraint graphs Hfor which the problem is identifiable for every Gand show that there are identifiable constraint graphs for which one cannot hope to learn every graph Gefficiently. We provide refined results for the case of proper vertexq-colorings of graphs of maximum degree d. In particular, we prove that in the tree uniqueness region (i.e., whenq≤ d), the problem is identifiable and we can learnGin poly(d,q)× O(n2logn) time. In the tree non-uniqueness region (i.e., when q≤ d), we show that the problem is not identifiable and thusGcannot be learned. Moreover, whenq ≤ d- √d + Θ (1), we establish that even learning an equivalent graph (any graph with the same set ofH-colorings) is computationally hard—sample complexity is exponential innin the worst case. We further explore the connection between the efficiency/hardness of the structure learning problem and the uniqueness/non-uniqueness phase transition for generalH-colorings and prove that under a well-known uniqueness condition in statistical physics, we can learnGin poly(d,q)× O(n2logn) time.

For spin systems, such as the hard-core model on independent sets weighted by fugacity lambda>0, efficient algorithms for the associated approximate counting/sampling problems typically apply in the high-temperature region, corresponding to low fugacity. Recent work of Jenssen, Keevash and Perkins (2019) yields an FPTAS for approximating the partition function (and an efficient sampling algorithm) on bounded-degree (bipartite) expander graphs for the hard-core model at sufficiently high fugacity, and also the ferromagnetic Potts model at sufficiently low temperatures. Their method is based on using the cluster expansion to obtain a complex zero-free region for the partition function of a polymer model, and then approximating this partition function using the polynomial interpolation method of Barvinok. We present a simple discrete-time Markov chain for abstract polymer models, and present an elementary proof of rapid mixing of this new chain under sufficient decay of the polymer weights. Applying these general polymer results to the hard-core and ferromagnetic Potts models on bounded-degree (bipartite) expander graphs yields fast algorithms with running time O(n log n) for the Potts model and O(n^2 log n) for the hard-core model, in contrast to typical running times of n^{O(log Delta)} for algorithms based on Barvinok’s polynomial interpolation method on graphs of maximum degree Delta. In addition, our approach via our polymer model Markov chain is conceptually simpler as it circumvents the zero-free analysis and the generalization to complex parameters. Finally, we combine our results for the hard-core and ferromagnetic Potts models with standard Markov chain comparison tools to obtain polynomial mixing time for the usual spin system Glauber dynamics restricted to even and odd or "red" dominant portions of the respective state spaces.

We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to e^{-f} where f:R^d -> R is mu-strongly convex and L-smooth (the condition number is kappa = L/mu). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is O(kappa), improving on the previous best bound of O(kappa^{1.5}); we complement this with an example where the relaxation time is Omega(kappa). When implemented using a nearly optimal ODE solver, HMC returns an epsilon-approximate point in 2-Wasserstein distance using O~((kappa d)^{0.5} epsilon^{-1}) gradient evaluations per step and O~((kappa d)^{1.5}epsilon^{-1}) total time.

We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model $M$ and a sampling oracle for the distribution $\mu_{M^*}$ of an unknown model $M^*$, can we efficiently determine if the two models $M$ and $M^*$ are the same? We consider identity testing for both soft-constraint and hard-constraint systems. In particular, we prove hardness results in two prototypical cases, the \emph{Ising model} and \emph{proper colorings}, and explore whether identity testing is easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalasis et al. (2018) presented a polynomial time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a super-polynomial number of samples. Specifically, for $n$-vertex graphs of maximum degree $d$, we prove that if $|\beta| d = \omega(\log{n})$ (where $\beta$ is the inverse temperature parameter), then there is no identity testing algorithm for the antiferromagnetic Ising model that runs in polynomial time unless $RP\!=\!NP$. We also establish computational lower bounds for a broader set of parameters under the (randomized) exponential time hypothesis. In our proofs, we use random graphs as gadgets; this is inspired by similar constructions in seminal works on the hardness of approximate counting. In the hard-constraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of \textsc{#BIS}, the problem of (approximately) counting independent sets in bipartite graphs. In particular, we prove that identity testing for colorings is hard in the same range of parameters where structure learning is known to be hard, which in turn matches the parameter regime for NP-hardness of the corresponding decision problem.

We study the structure learning problem for $H$-colorings, an important class of Markov random fields that capture key combinatorial structures on graphs, including proper colorings and independent sets, as well as spin systems from statistical physics. The learning problem is as follows: for a fixed (and known) constraint graph $H$ with $q$ colors and an unknown graph $G=(V,E)$ with $n$ vertices, given uniformly random $H$-colorings of $G$, how many samples are required to learn the edges of the unknown graph $G$? We give a characterization of $H$ for which the problem is identifiable for every $G$, i.e., we can learn $G$ with an infinite number of samples. We also show that there are identifiable constraint graphs for which one cannot hope to learn every graph $G$ efficiently. We focus particular attention on the case of proper vertex $q$-colorings of graphs of maximum degree $d$ where intriguing connections to statistical physics phase transitions appear. We prove that in the tree uniqueness region (i.e., when $q>d$) the problem is identifiable and we can learn $G$ in $\mathsf{poly}(d,q)\times O(n^2\log{n})$ time. In contrast for soft-constraint systems, such as the Ising model, the best possible running time is exponential in $d$. In the tree non-uniqueness region (i.e., when $q≤d$) we prove that the problem is not identifiable and thus $G$ cannot be learned. Moreover, when $q Cite this Paper BibTeX @InProceedings{pmlr-v83-blanca18a, title = {Structure Learning of ${H}$-colorings}, author = {Blanca, Antonio and Chen, Zongchen and Štefankovič, Daniel and Vigoda, Eric}, booktitle = {Proceedings of Algorithmic Learning Theory}, pages = {152--185}, year = {2018}, editor = {Janoos, Firdaus and Mohri, Mehryar and Sridharan, Karthik}, volume = {83}, series = {Proceedings of Machine Learning Research}, month = {07--09 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v83/blanca18a/blanca18a.pdf}, url = {https://proceedings.mlr.press/v83/blanca18a.html}, abstract = {We study the structure learning problem for $H$-colorings, an important class of Markov random fields that capture key combinatorial structures on graphs, including proper colorings and independent sets, as well as spin systems from statistical physics. The learning problem is as follows: for a fixed (and known) constraint graph $H$ with $q$ colors and an unknown graph $G=(V,E)$ with $n$ vertices, given uniformly random $H$-colorings of $G$, how many samples are required to learn the edges of the unknown graph $G$? We give a characterization of $H$ for which the problem is identifiable for every $G$, i.e., we can learn $G$ with an infinite number of samples. We also show that there are identifiable constraint graphs for which one cannot hope to learn every graph $G$ efficiently. We focus particular attention on the case of proper vertex $q$-colorings of graphs of maximum degree $d$ where intriguing connections to statistical physics phase transitions appear. We prove that in the tree uniqueness region (i.e., when $q>d$) the problem is identifiable and we can learn $G$ in $\mathsf{poly}(d,q)\times O(n^2\log{n})$ time. In contrast for soft-constraint systems, such as the Ising model, the best possible running time is exponential in $d$. In the tree non-uniqueness region (i.e., when $q≤d$) we prove that the problem is not identifiable and thus $G$ cannot be learned. Moreover, when $q Copy to Clipboard Download Endnote %0 Conference Paper %T Structure Learning of ${H}$-colorings %A Antonio Blanca %A Zongchen Chen %A Daniel Štefankovič %A Eric Vigoda %B Proceedings of Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Firdaus Janoos %E Mehryar Mohri %E Karthik Sridharan %F pmlr-v83-blanca18a %I PMLR %P 152--185 %U https://proceedings.mlr.press/v83/blanca18a.html %V 83 %X We study the structure learning problem for $H$-colorings, an important class of Markov random fields that capture key combinatorial structures on graphs, including proper colorings and independent sets, as well as spin systems from statistical physics. The learning problem is as follows: for a fixed (and known) constraint graph $H$ with $q$ colors and an unknown graph $G=(V,E)$ with $n$ vertices, given uniformly random $H$-colorings of $G$, how many samples are required to learn the edges of the unknown graph $G$? We give a characterization of $H$ for which the problem is identifiable for every $G$, i.e., we can learn $G$ with an infinite number of samples. We also show that there are identifiable constraint graphs for which one cannot hope to learn every graph $G$ efficiently. We focus particular attention on the case of proper vertex $q$-colorings of graphs of maximum degree $d$ where intriguing connections to statistical physics phase transitions appear. We prove that in the tree uniqueness region (i.e., when $q>d$) the problem is identifiable and we can learn $G$ in $\mathsf{poly}(d,q)\times O(n^2\log{n})$ time. In contrast for soft-constraint systems, such as the Ising model, the best possible running time is exponential in $d$. In the tree non-uniqueness region (i.e., when $q≤d$) we prove that the problem is not identifiable and thus $G$ cannot be learned. Moreover, when $q Copy to Clipboard Download APA Blanca, A., Chen, Z., Štefankovič, D. & Vigoda, E.. (2018). Structure Learning of ${H}$-colorings. Proceedings of Algorithmic Learning Theory, in Proceedings of Machine Learning Research 83:152-185 Available from https://proceedings.mlr.press/v83/blanca18a.html. Copy to Clipboard Download Related Material Download PDF This site last compiled Sun, 05 Jul 2026 15:11:54 +0000 Github Account Copyright © The authors and PMLR 2026. MLResearchPress

Nowadays, cloud storage systems may contain tens of thousands of servers and large scale data sets, which significantly require efficient data management scheme and query processing mechanism. To fulfill these requirements in modern data centers, the infrastructure of cloud systems, we propose FT-Index, a secondary indexing scheme for cloud system with switch-centric topology. FT-Index has a two-layer design. The upper-layer index, called global index, is distributed across different hosts in the system, while the lower-layer index, named local index, is a B+-tree for local query. We further adopt the Interval tree to reorganize the global index and propose two versions of FT-Index with different publishing methods to lower the rate of false positives and reduce the cost of forwarding queries. We provide detailed theoretical analysis on the upper bound of false positives, physical hops per query, and the relationship between them. We also conduct abundant experiments to validate the efficiency of FT-Index.