This work establishes novel optimum mixing bounds for the Glauber dynamics on the Hard-core and Ising models. These bounds are expressed in terms of the local connective constant of the underlying graph \(G\). This is a notion of effective degree for \(G\), and as such, it allows us to obtain mixing bounds which are inherently less restrictive than those obtained using other graph invariants, e.g., the maximum degree, the operator norm of the adjacency matrix, etc.

{\em Spin-glasses} are natural Gibbs distributions that have been studied in theoretical computer science for many decades. Recently, they have been gaining renewed attention from the community as they emerge naturally in {\em neural computation} and {\em learning}, {\em network inference}, {\em optimisation} and many other areas. Here we consider the {\em {2-spin model}} at inverse temperature $\beta$ when the underlying graph is an instance of $G(n,d/n)$, i.e., the random graph on $n$ vertices such that each edge appears independently with probability $d/n$, where the expected degree $d=\Theta(1)$. We study the problem of efficiently sampling from the aforementioned distribution using the well-known Markov chain called {\em Glauber dynamics}. For a certain range of $\beta$, that depends only on the expected degree $d$ of the graph, and for typical instances of the {2-spin model} on $G(n,d/n)$, we show that the corresponding (single-site) Glauber dynamics exhibits mixing time $O\left(n^{2+\frac{3}{\log^2 d}}\right)$. The range of $\beta$ for which we obtain our rapid mixing result corresponds to the expected influence being smaller than $1/d$. We establish our results by utilising the well-known {\em path-coupling} technique. In the standard setting of Glauber dynamics on $G(n,d/n)$ one has to deal with the so-called effect of high degree vertices. % in the path-coupling analysis. Here, with the spin-glasses, rather than considering vertex-degrees, it is more natural to use a different measure on the vertices of the graph, that we call {\em aggregate influence}. We build on the block-construction approach proposed by [Dyer, Flaxman, Frieze and Vigoda: 2006] to circumvent the problem with the high degrees in the path-coupling analysis. Specifically, to obtain our results, we first establish rapid mixing for an appropriately defined block-dynamics. We design this dynamics such that vertices of large aggregate influence are placed deep inside their blocks. Then, we obtain rapid mixing for the (single-site) Glauber dynamics by utilising a comparison argument.

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

Motivated by the theory of spin-glasses in physics, we study the so-called reconstruction problem on the tree, and on the sparse random graph G(n,d/n). Both cases reduce naturally to analysing broadcasting models, where each edge has its own broadcasting matrix, and this matrix is drawn independently from a predefined distribution. We establish the reconstruction threshold for the cases where the broadcasting matrices give rise to symmetric, 2-spin Gibbs distributions. This threshold seems to be a natural extension of the well-known Kesten-Stigum bound that manifests in the classic version of the reconstruction problem. Our results determine, as a special case, the reconstruction threshold for the prominent Edwards–Anderson model of spin-glasses, on the tree. Also, we extend our analysis to the setting of the Galton-Watson random tree, and the (sparse) random graph G(n,d/n), where we establish the corresponding thresholds. Interestingly, for the Edwards–Anderson model on the random graph, we show that the replica symmetry breaking phase transition, established by Guerra and and Toninelli in [Guerra and Toninelli, 2004], coincides with the reconstruction threshold. Compared to classical Gibbs distributions, spin-glasses have several unique features. In that respect, their study calls for new ideas, e.g. we introduce novel estimators for the reconstruction problem. The main technical challenge in the analysis of such systems, is the presence of (too) many levels of randomness, which we manage to circumvent by utilising recently proposed tools coming from the analysis of Markov chains.

In this paper, we present a novel, polynomial time, algorithm for approximate sampling from symmetric Gibbs distributions on the sparse random graph and hypergraph. The examples of symmetric distributions we consider here include some important distributions on spin-systems and spin-glasses. These are: the q-state antiferromagnetic Potts model for q ≥ 2, including the (hyper)graph Ising model and random colourings. The uniform distribution over the Not-All-Equal solutions of a random k-SAT formula. Finally, we consider sampling from the spin-glass distribution called the k-spin model, i.e., this is the "diluted" version of the well-known Sherrington-Kirkpatrick model. Spin-glasses give rise to very intricate distributions which are also studied in mathematics, in neural computation, computational biology and many other areas. To our knowledge, this is the first rigorously analysed efficient sampling algorithm for spin-glasses which operates in a non trivial range of the parameters of the distribution. We present, what we believe to be, an elegant sampling algorithm. Our algorithm is unique in its approach and does not belong to any of the well-known families of sampling algorithms. We derive it by investigating the power and the limits of the approach that was introduced in [Efthymiou: SODA 2012] and combine it, in a novel way, with powerful notions from the Cavity method. Specifically, for a symmetric Gibbs distribution μ on the random (hyper)graph whose parameters are within an appropriate range, our sampling algorithm has the following properties: with probability 1-o(1) over the instances of the input (hyper)graph, it generates a configuration which is distributed within total variation distance n^{-Ω(1)} from μ. The time complexity is O((nlog n)²), where n is the size of the input (hyper)graph. We make a notable progress regarding impressive predictions of physicists relating phase-transitions of Gibbs distributions with the efficiency of the corresponding sampling algorithms. For most (if not all) the cases we consider here, our algorithm outperforms by far any other sampling algorithms in terms of the permitted range of the parameters of the Gibbs distributions. The use of notions and ideas from the Cavity method provides a new insight to the sampling problem. Our results imply that there is a lot of potential for further exploiting the Cavity method for algorithmic design.

Strong spatial mixing (SSM) is a form of correlation decay that has played an essential role in the design of approximate counting algorithms for spin systems. A notable example is the algorithm of Weitz (2006) for the hard-core model on weighted independent sets. We study SSM for the q-colorings problem on the infinite (d+1)-regular tree. Weak spatial mixing (WSM) captures whether the influence of the leaves on the root vanishes as the height of the tree grows. Jonasson (2002) established WSM when q>d+1. In contrast, in SSM, we first fix a coloring on a subset of internal vertices, and we again ask if the influence of the leaves on the root is vanishing. It was known that SSM holds on the (d+1)-regular tree when q>alpha d where alpha ~~ 1.763... is a constant that has arisen in a variety of results concerning random colorings. Here we improve on this bound by showing SSM for q>1.59d. Our proof establishes an L^2 contraction for the BP operator. For the contraction we bound the norm of the BP Jacobian by exploiting combinatorial properties of the coloring of the tree.

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

We study the mixing properties of the single-site Markov chain known as the Glauber dynamics for sampling k-colorings of a sparse random graph G(n, d/n) for constant d. The best known rapid mixing results for general graphs are in terms of the maximum degree Δ of the input graph G and hold when k > 11Δ/6 for all G. Improved results hold when k > αΔ for graphs with girth ≥ 5 and Δ sufficiently large where α ≈ 1.7632 … is the root of α = exp(1/α); further improvements on the constant α hold with stronger girth and maximum degree assumptions. For sparse random graphs the maximum degree is a function of n and the goal is to obtain results in terms of the expected degree d. The following rapid mixing results for G(n,d/n) hold with high probability over the choice of the random graph for sufficiently large constant d. Mossel and Sly (2009) proved rapid mixing for constant k, and Efthymiou (2014) improved this to k linear in d. The condition was improved to k > 3d by Yin and Zhang (2016) using non-MCMC methods. Here we prove rapid mixing when k > αd where α ≈ 1.7632 … is the same constant as above. Moreover we obtain O(n3) mixing time of the Glauber dynamics, while in previous rapid mixing results the exponent was an increasing function in d. Our proof analyzes an appropriately defined block dynamics to “hide” high-degree vertices. One new aspect in our improved approach is utilizing so-called local uniformity properties for the analysis of block dynamics. To analyze the “burn-in” phase we prove a concentration inequality for the number of disagreements propagating in large blocks.

Diluted mean-field models are spin systems whose geometry of interactions is induced by a sparse random graph or hypergraph. Such models play an eminent role in the statistical mechanics of disordered systems as well as in combinatorics and computer science. In a path-breaking paper based on the non-rigorous `cavity method', physicists predicted not only the existence of a replica symmetry breaking phase transition in such models but also sketched a detailed picture of the evolution of the Gibbs measure within the replica symmetric phase and its impact on important problems in combinatorics, computer science and physics [Krzakala et al.: PNAS 2007]. In this paper we rigorise this picture completely for a broad class of models, encompassing the Potts antiferromagnet on the random graph, the $k$-XORSAT model and the diluted $k$-spin model for even $k$. We also prove a conjecture about the detection problem in the stochastic block model that has received considerable attention [Decelle et al.: Phys. Rev. E 2011].

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(Δ).

Approximate random $k$-coloring of a graph $G$ is a well-studied problem in computer science and statistical physics. It amounts to constructing a $k$-coloring of $G$ which is distributed close to the Gibbs distribution in polynomial time. Here, we deal with the problem when the underlying graph is an instance of the Erdös--Rényi random graph $G(n,d/n)$, where $d$ is a sufficiently large constant. We propose a novel efficient algorithm for approximate random $k$-coloring $G(n,d/n)$ for any $k\geq (1+\epsilon)d$. To be more specific, with probability at least $1-n^{-\Omega(1)}$ over the input instances $G(n,d/n)$ and for $k\geq (1+\epsilon)d$, the algorithm returns a $k$-coloring which is distributed within total variation distance $n^{-\Omega(1)}$ from the Gibbs distribution of the input graph instance. The algorithm we propose is neither Markov chain Monte Carlo nor inspired by the message-passing algorithms proposed by statistical physicists. Roughly, the idea is as follows. Initially we remove sufficiently many edges of the input graph. This results in a “simple graph” which can be $k$-colored randomly efficiently. The algorithm colors randomly this simple graph. Then it puts back the removed edges one by one. Every time a new edge is put back the algorithm updates the coloring of the graph so that the coloring remains random. The performance of the algorithm depends heavily on certain spatial correlation decay properties of the Gibbs distribution.

The broadcasting models on trees arise in many contexts such as discrete mathematics, biology, information theory, statistical physics and computer science. In this work, we consider the k-colouring model. A basic question here is whether the assignment at the root affects the distribution of the colourings at the vertices at distance h from the root. This is the so-called reconstruction problem. For the case where the underlying tree is d -ary it is well known that d/ln(d) is the reconstruction threshold. That is, for k=(1+epsilon)*d/ln(d) we have non-reconstruction while for k=(1-epsilon)*d/ln(d) we have reconstruction. Here, we consider the largely unstudied case where the underlying tree is chosen according to a predefined distribution. In particular, we consider the well-known Galton-Watson trees. The corresponding model arises naturally in many contexts such as the theory of spin-glasses and its applications on random Constraint Satisfaction Problems (rCSP). The study on rCSP focuses on Galton-Watson trees with offspring distribution B(n,d/n), i.e. the binomial with parameters n and d/n, where d is fixed. Here we consider a broader version of the problem, as we assume general offspring distribution which includes B(n,d/n) as a special case. Our approach relates the corresponding bounds for (non)reconstruction to certain concentration properties of the offspring distribution. This allows to derive reconstruction thresholds for a very wide family of offspring distributions, which includes B(n,d/n). A very interesting corollary is that for distributions with expected offspring d, we get reconstruction threshold d/ln(d) under weaker concentration conditions than what we have in B(n,d/n). Furthermore, our reconstruction threshold for the random colorings of Galton-Watson with offspring B(n,d/n), implies the reconstruction threshold for the random colourings of G(n,d/n).

Sampling from the Gibbs distribution is a well studied problem in computer science as well as in statistical physics. In this work we focus on the k-colouring model and the hard-core model with fugacity λ when the underlying graph is an instance of Erdős-Rényi random graph G(n, p), where p = d/n and d is fixed. We use the Markov Chain Monte Carlo method for sampling from the aforementioned distributions. In particular, we consider Glauber (block) dynamics. We show a dramatic improvement on the bounds for rapid mixing in terms of the number of colours and the fugacity for the corresponding models. For both models the bounds we get are only within small constant factors from the conjectured ones by the statistical physicists. We use Path Coupling to show rapid mixing. For k and λ in the range of our interest the technical challenge is to cope with the high degree vertices, i.e. vertices of degree much larger than the expected degree d. The usual approach to this problem is to consider block updates rather than single vertex updates for the Markov chain. Taking appropriately defined blocks the effect of high degree vertices diminishes. However devising such a block construction is a non trivial task. We develop for a first time a weighting schema for the paths of the underlying graph. Only, vertices which belong to “light” paths can be placed at the boundaries of the blocks. The tree-like local structure of G(n, d/n) allows the construction of simple structured blocks.

Approximate random k-colouring of a graph G = (V, E) is a very well studied problem in computer science and statistical physics. It amounts to constructing a k-colouring of G which is distributed close to Gibbs distribution, i.e. the uniform distribution over all the k-colourings of G. Here, we deal with the problem when the underlying graph is an instance of Erdős-Rényi random graph G(n, p), where p = d/n and d is fixed. We propose a novel efficient algorithm for approximate random k-colouring with the following properties: given an instance of G(n, d/n) and for any k > (2 + ∊)d, it returns a k-colouring distributed within total variation distance n−Ω(1) from the Gibbs distribution, with probability 1 – n−Ω(1). What we propose is neither a MCMC algorithm nor some algorithm inspired by the message passing heuristics that were introduced by statistical physicists. Our algorithm is of combinatorial nature. It is based on a rather simple recursion which reduces the random k-colouring of G(n, d/n) to random k-colouring simpler subgraphs first. The lower bound on the number of colours for our algorithm to run in polynomial time is significantly smaller than the corresponding bounds we have for any previous algorithm.

The independence number of a sparse random graph G(n, m) of average degree d = 2m/n is well-known to be α(G(n, m)) ∼ 2n ln(d)/d with high probability. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size (1 + o(1)) · n ln(d)/d, i.e., half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with (1 + ε)n ln(d)/d, for any fixed ε > 0. In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point k ∼ n ln(d)/d. Roughly speaking, we prove that independent sets of size k > (1 + ε)n ln(d)/d form an intricately ragged landscape, in which local search algorithms are bound to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independents sets.