Abstract We consider spin systems on general n -vertex graphs of unbounded degree and explore the effects of spectral independence on the rate of convergence to equilibrium of global Markov chains. Spectral independence is a novel way of quantifying the decay of correlations in spin system models, which has significantly advanced the study of Markov chains for spin systems. We prove that whenever spectral independence holds, the popular Swendsen–Wang dynamics for the q -state ferromagnetic Potts model on graphs of maximum degree $$\Delta $$ , where $$\Delta $$ is allowed to grow with n , converges in $$O((\Delta \log n)^c)$$ steps where $$c > 0$$ is a constant independent of $$\Delta $$ and n . We also show a similar mixing time bound for the block dynamics of general spin systems, again assuming that spectral independence holds. Finally, for monotone spin systems such as the Ising model and the hardcore model on bipartite graphs, we show that spectral independence implies that the mixing time of the systematic scan dynamics is $$O(\Delta ^c \log n)$$ for a constant $$c>0$$ independent of $$\Delta $$ and n . Systematic scan dynamics are widely popular but are notoriously difficult to analyze. Our result implies optimal $$O(\log n)$$ mixing time bounds for any systematic scan dynamics of the ferromagnetic Ising model on general graphs up to the tree uniqueness threshold. Our main technical contribution is an improved factorization of the entropy functional: this is the common starting point for all our proofs. Specifically, we establish the so-called k -partite factorization of entropy with a constant that depends polynomially on the maximum degree of the graph.

We study the speed of convergence of the Swendsen-Wang (SW) dynamics for the q-state ferromagnetic Potts model on the n-vertex complete graph, known as the mean-field model. The SW dynamics was introduced as an attractive alternative to the local Glauber dynamics, often offering faster convergence rates to stationarity in a variety of settings. A series of works have characterized the asymptotic behavior of the speed of convergence of the mean-field SW dynamics for all q ≥ 2 and all values of the inverse temperature parameter β > 0. In particular, it is known that when β > q the mixing time of the SW dynamics is Θ(log n). We strengthen this result by showing that for all β > q, there exists a constant c(β,q) > 0 such that the mixing time of the SW dynamics is c(β,q) log n + Θ(1). This implies that the mean-field SW dynamics exhibits the cutoff phenomenon in this temperature regime, demonstrating that this Markov chain undergoes a sharp transition from "far from stationarity" to "well-mixed" within a narrow Θ(1) time window. The presence of cutoff is algorithmically significant, as simulating the chain for fewer steps than its mixing time could lead to highly biased samples.

A common obstruction to efficient sampling from high-dimensional distributions with Markov chains is the multimodality of the target distribution because they may get trapped far from stationarity. Still, one hopes that this is only a barrier to the mixing of Markov chains from worst-case initializations and can be overcome by choosing high-entropy initializations, e.g., a product or weakly correlated distribution. Ideally, from such initializations, the dynamics would escape from the saddle points separating modes quickly and spread its mass between the dominant modes with the correct probabilities.

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.

We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets ) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.

We consider spin systems on general $n$-vertex graphs of unbounded degree and explore the effects of spectral independence on the rate of convergence to equilibrium of global Markov chains. Spectral independence is a novel way of quantifying the decay of correlations in spin system models, which has significantly advanced the study of Markov chains for spin systems. We prove that whenever spectral independence holds, the popular Swendsen--Wang dynamics for the $q$-state ferromagnetic Potts model on graphs of maximum degree $Δ$, where $Δ$ is allowed to grow with $n$, converges in $O((Δ\log n)^c)$ steps where $c > 0$ is a constant independent of $Δ$ and $n$. We also show a similar mixing time bound for the block dynamics of general spin systems, again assuming that spectral independence holds. Finally, for monotone spin systems such as the Ising model and the hardcore model on bipartite graphs, we show that spectral independence implies that the mixing time of the systematic scan dynamics is $O(Δ^c \log n)$ for a constant $c>0$ independent of $Δ$ and $n$. Systematic scan dynamics are widely popular but are notoriously difficult to analyze. Our result implies optimal $O(\log n)$ mixing time bounds for any systematic scan dynamics of the ferromagnetic Ising model on general graphs up to the tree uniqueness threshold. Our main technical contribution is an improved factorization of the entropy functional: this is the common starting point for all our proofs. Specifically, we establish the so-called $k$-partite factorization of entropy with a constant that depends polynomially on the maximum degree of the graph.

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.

Sampling from the q-state ferromagnetic Potts model is a fundamental question in statistical physics, probability theory, and theoretical computer science. On general graphs, this problem is computationally hard, and this hardness holds at arbitrarily low temperatures. At the same time, in recent years, there has been significant progress showing the existence of low-temperature sampling algorithms in various specific families of graphs. Our aim in this paper is to understand the minimal structural properties of general graphs that enable polynomial-time sampling from the q-state ferromagnetic Potts model at low temperatures. We study this problem from the perspective of the widely-used Swendsen-Wang dynamics and the closely related random-cluster dynamics. These are non-local Markov chains that have long been believed to converge rapidly to equilibrium at low temperatures in many graphs. However, the hardness of the sampling problem likely indicates that this is not even the case for all bounded degree graphs. Our results demonstrate that a key graph property behind fast or slow convergence time for these dynamics is whether the independent edge-percolation on the graph admits a strongly supercritical phase. By this, we mean that at large $p\lt 1$, it has a large linear-sized component, and the graph complement of that component is comprised of only small components Specifically, we prove that such a condition implies fast mixing of the Swendsen-Wang and random-cluster dynamics on two general families of bounded-degree graphs: (a) graphs of at most stretched-exponential volume growth and (b) locally treelike graphs. In the other direction, we show that, even among graphs in those families, these Markov chains can converge exponentially slowly at arbitrarily low temperatures if the edge-percolation condition does not hold. In the process, we develop new tools for the analysis of non-local Markov chains, including a framework to bound the speed of disagreement propagation in the presence of long-range correlations, an understanding of spatial mixing properties on trees with random boundary conditions, and an analysis of burn-in phases at low temperatures.

We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.

We consider the problem of sampling from the ferromagnetic Potts and random-cluster models on a general family of random graphs via the Glauber dynamics for the random-cluster model. The random-cluster model is parametrized by an edge probability p ∈ (0,1) and a cluster weight q > 0. We establish that for every q ≥ 1, the random-cluster Glauber dynamics mixes in optimal Θ(nlog n) steps on n-vertex random graphs having a prescribed degree sequence with bounded average branching γ throughout the full high-temperature uniqueness regime p < p_u(q,γ). The family of random graph models we consider includes the Erdős-Rényi random graph G(n,γ/n), and so we provide the first polynomial-time sampling algorithm for the ferromagnetic Potts model on Erdős-Rényi random graphs for the full tree uniqueness regime. We accompany our results with mixing time lower bounds (exponential in the largest degree) for the Potts Glauber dynamics, in the same settings where our Θ(n log n) bounds for the random-cluster Glauber dynamics apply. This reveals a novel and significant computational advantage of random-cluster based algorithms for sampling from the Potts model at high temperatures.

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.

MOTIVATION: Sketching is now widely used in bioinformatics to reduce data size and increase data processing speed. Sketching approaches entice with improved scalability but also carry the danger of decreased accuracy and added bias. In this article, we investigate the minimizer sketch and its use to estimate the Jaccard similarity between two sequences. RESULTS: We show that the minimizer Jaccard estimator is biased and inconsistent, which means that the expected difference (i.e. the bias) between the estimator and the true value is not zero, even in the limit as the lengths of the sequences grow. We derive an analytical formula for the bias as a function of how the shared k-mers are laid out along the sequences. We show both theoretically and empirically that there are families of sequences where the bias can be substantial (e.g. the true Jaccard can be more than double the estimate). Finally, we demonstrate that this bias affects the accuracy of the widely used mashmap read mapping tool. AVAILABILITY AND IMPLEMENTATION: Scripts to reproduce our experiments are available at https://github.com/medvedevgroup/minimizer-jaccard-estimator/tree/main/reproduce. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

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.

The random-cluster model is a unifying framework for studying random graphs, spin systems and electrical networks that plays a fundamental role in designing efficient Markov Chain Monte Carlo (MCMC) sampling algorithms for the classical ferromagnetic Ising and Potts models. In this paper, we study a natural non-local Markov chain known as the Chayes-Machta dynamics for the mean-field case of the random-cluster model, where the underlying graph is the complete graph on $n$ vertices. The random-cluster model is parametrized by an edge probability $p$ and a cluster weight $q$. Our focus is on the critical regime: $p = p_c(q)$ and $q \in (1,2)$, where $p_c(q)$ is the threshold corresponding to the order-disorder phase transition of the model. We show that the mixing time of the Chayes-Machta dynamics is $O(\log n \cdot \log \log n)$ in this parameter regime, which reveals that the dynamics does not undergo an exponential slowdown at criticality, a surprising fact that had been predicted (but not proved) by statistical physicists. This also provides a nearly optimal bound (up to the $\log\log n$ factor) for the mixing time of the mean-field Chayes-Machta dynamics in the only regime of parameters where no non-trivial bound was previously known. Our proof consists of a multi-phased coupling argument that combines several key ingredients, including a new local limit theorem, a precise bound on the maximum of symmetric random walks with varying step sizes, and tailored estimates for critical random graphs. In addition, we derive an improved comparison inequality between the mixing time of the Chayes-Machta dynamics and that of the local Glauber dynamics on general graphs; this results in better mixing time bounds for the local dynamics in the mean-field setting.

We study the mixing time of the Swendsen-Wang dynamics for the ferromagnetic Ising and Potts models on the integer lattice ℤd. This dynamics is a widely used Markov chain that has largely resisted sharp analysis because it is non-local, i.e., it changes the entire configuration in one step. We prove that, whenever strong spatial mixing (SSM) holds, the mixing time on any n-vertex cube in ℤd is O(logn), and we prove this is tight by establishing a matching lower bound. The previous best known bound was O(n). SSM is a standard condition corresponding to exponential decay of correlations with distance between spins on the lattice and is known to hold in d=2 dimensions throughout the high-temperature (single phase) region. Our result follows from a modified log-Sobolev inequality, which expresses the fact that the dynamics contracts relative entropy at a constant rate at each step. The proof of this fact utilizes a new factorization of the entropy in the joint probability space over spins and edges that underlies the Swendsen-Wang dynamics, which extends to general bipartite graphs of bounded degree. This factorization leads to several additional results, including mixing time bounds for a number of natural local and non-local Markov chains on the joint space, as well as for the standard random-cluster dynamics.

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.

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 consider the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the so-called uniqueness regime of the regular tree, but positive algorithmic results have been for the most part elusive. In this paper, for all integers $q\geq 3$ and $\Delta\geq 3$, we develop algorithms that produce samples within error $o(1)$ from the $q$-state Potts model on random $\Delta$-regular graphs, whenever the temperature is in uniqueness, for both the ferromagnetic and antiferromagnetic cases. The algorithm for the antiferromagnetic Potts model is based on iteratively adding the edges of the graph and resampling a bichromatic class that contains the endpoints of the newly added edge. Key to the algorithm is how to perform the resampling step efficiently since bichromatic classes can potentially induce linear-sized components. To this end, we exploit the tree uniqueness to show that the average growth of bichromatic components is typically small, which allows us to use correlation decay algorithms for the resampling step. While the precise uniqueness threshold on the tree is not known for general values of $q$ and $\Delta$ in the antiferromagnetic case, our algorithm works throughout uniqueness regardless of its value. In the case of the ferromagnetic Potts model, we are able to simplify the algorithm significantly by utilizing the random-cluster representation of the model. In particular, we demonstrate that a percolation-type algorithm succeeds in sampling from the random-cluster model with parameters $p,q$ on random $\Delta$-regular graphs for all values of $q\geq 1$ and $p

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.

The random-cluster (FK) model is a key tool for the study of phase transitions and for the design of efficient Markov chain Monte Carlo (MCMC) sampling algorithms for the Ising/Potts model. It is well-known that in the high-temperature region beta 1 and p != p_c(q) the mixing time of the FK-dynamics is polynomial in n for every realizable boundary condition. Previously, for boundary conditions that do not carry long-range information (namely wired and free), Blanca and Sinclair (2017) had proved that the FK-dynamics in the same setting mixes in optimal O(n^2 log n) time. To illustrate the difficulties introduced by general boundary conditions, we also construct a class of non-realizable boundary conditions that induce slow (stretched-exponential) convergence at high temperatures.

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

We consider the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the uniqueness regime of the regular tree, but positive algorithmic results have been for the most part elusive. In this paper, for all integers $q\geq 3$ and $Δ\geq 3$, we develop algorithms that produce samples within error $o(1)$ from the $q$-state Potts model on random $Δ$-regular graphs, whenever the temperature is in uniqueness, for both the ferromagnetic and antiferromagnetic cases. The algorithm for the antiferromagnetic Potts model is based on iteratively adding the edges of the graph and resampling a bichromatic class that contains the endpoints of the newly added edge. Key to the algorithm is how to perform the resampling step efficiently since bichromatic classes may induce linear-sized components. To this end, we exploit the tree uniqueness to show that the average growth of bichromatic components is typically small, which allows us to use correlation decay algorithms for the resampling step. While the precise uniqueness threshold on the tree is not known for general values of $q$ and $Δ$ in the antiferromagnetic case, our algorithm works throughout uniqueness regardless of its value. In the case of the ferromagnetic Potts model, we simplify the algorithm significantly by utilising the random-cluster representation of the model. In particular, we show that a percolation-type algorithm succeeds in sampling from the random-cluster model with parameters $p,q$ on random $Δ$-regular graphs for all values of $q\geq 1$ and $p

The random-cluster model has been widely studied as a unifying framework for random graphs, spin systems and electrical networks, but its dynamics have so far largely resisted analysis. In this paper we analyze the Glauber dynamics of the random-cluster model in the canonical case where the underlying graph is an n × n box in the Cartesian lattice ℤ2. Our main result is a O(n2 log n) upper bound for the mixing time at all values of the model parameter p except the critical point p = pc(q), and for all values of the second model parameter q ≥ 1. We also provide a matching lower bound proving that our result is tight. Our analysis takes as its starting point the recent breakthrough by Beffara and Duminil-Copin on the location of the random-cluster phase transition in ℤ2. It is reminiscent of similar results for spin systems such as the Ising and Potts models, but requires the reworking of several standard tools in the context of the random-cluster model, which is not a spin system in the usual sense.

The random-cluster model has been widely studied as a unifying framework for random graphs, spin systems and random spanning trees, but its dynamics have so far largely resisted analysis. In this paper we study a natural non-local Markov chain known as the Chayes-Machta dynamics for the mean-field case of the random-cluster model, and identify a critical regime (lambda_s,lambda_S) of the model parameter lambda in which the dynamics undergoes an exponential slowdown. Namely, we prove that the mixing time is Theta(log n) if lambda is not in [lambda_s,lambda_S], and e^Omega(sqrt{n}) when lambda is in (lambda_s,lambda_S). These results hold for all values of the second model parameter q > 1. In addition, we prove that the local heat-bath dynamics undergoes a similar exponential slowdown in (lambda_s,lambda_S).

A universal cycle (u-cycle) is a compact listing of a collection of combinatorial objects. In this paper, we use natural encodings of these objects to show the existence of u-cycles for collections of subsets, restricted multisets, and lattice paths. For subsets, we show that a u-cycle exists for the k-subsets of an n-set if we let k vary in a non zero length interval. We use this result to construct a “covering” of length $(1+o(1))$$n \choose k$ for all subsets of $[n]$ of size exactly k with a specific formula for the $o(1)$ term. We also show that u-cycles exist for all n-length words over some alphabet $\Sigma,$ which contain all characters from $R \subset \Sigma.$ Using this result we provide u-cycles for encodings of Sperner families of size 2 and proper chains of subsets.