Search

Spin-glasses are Gibbs distributions that have been studied in CS for many decades. Recently, they have gained renewed attention as they emerge naturally in learning, inference, optimisation etc. We consider the Edwards-Anderson (EA) spin-glass distribution at inverse temperature $\beta$ when the underlying graph is an instance of $G(n,d/n)$. This is the random graph on $n$ vertices where each edge appears independently with probability $d/n$ and $d=\Theta(1)$. We study the problem of approximate sampling from this distribution using Glauber dynamics. For a range of $\beta$ that depends on $d$ and for typical instances of the EA model on $G(n,d/n)$, we show that the corresponding Glauber dynamics exhibits mixing time $O(n^{2+\frac{3}{\log^2 d}})$. The range of $\beta$ for which we obtain our rapid-mixing results correspond to the expected influence being $<1/d$; we conjecture that this is the best possible. Unlike the mean-field spin-glasses, where the problem has been studied before, the diluted case has not. We utilise the well-known path-coupling technique. In the standard Glauber dynamics on $G(n,d/n)$, one has to deal with the so-called effect of high degree vertices. Here, rather than considering degrees, it is more natural to use a different measure on the vertices called aggregate influence. We build on the block-construction approach proposed by [Dyer et al. 2006] to circumvent the problem of high-degree vertices. Specifically, 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 Glauber dynamics utilising a comparison argument., Comment: 44 pages

Motivated by the theory of spin-glasses in physics, we study the so-called reconstruction problem for the related distributions on the tree, and on the sparse random graph $G(n,d/n)$. Both cases, reduce naturally to studying broadcasting models on the tree, where each edge has its own broadcasting matrix, and this matrix is drawn independently from a predefined distribution. In this context, we study the effect of the configuration at the root to that of the vertices at distance $h$, as $h\to\infty$. 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 which arises in the classic version of the reconstruction problem. Our results imply, as a special case, the reconstruction threshold for the well-known Edward-Anderson model of spin-glasses on the tree. Also, we extend our analysis to the setting of the Galton-Watson tree, and the random graph $G(n,d/n)$, where we establish the corresponding thresholds.Interestingly, for the Edward-Anderson model on the random graph, we show that the replica symmetry breaking phase transition, established in [Guerra and Toninelli:2004], coincides with the reconstruction threshold. Compared to the classical Gibbs distributions, the spin-glasses have a lot of unique features. In that respect, their study calls for new ideas, e.g., we introduce novel estimators for the reconstruction problem. Furthermore, note that the main technical challenge in the analysis is the presence of (too) many levels of randomness. We manage to circumvent this problem by utilising recently proposed tools coming from the analysis of Markov chains.

We study the single-site Glauber dynamics for the fugacity $\lambda$, 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 fugacity $\lambda < \frac{d^d}{(d-1)^{d+1}}$, the mixing time of Glauber dynamics is $n^{1 + O(1/\log \log n)}$. Our result improves on the recent elegant algorithm in [Bezakova, Galanis, Goldberg Stefankovic; ICALP'22]. The algorithm there is a 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 Bezakova et al. paper, hence our algorithm is also faster. The main challenge in our proof is handling vertices with unbounded degrees. We provide stronger results with regard the spectral independence via branching values and show that the our Gibbs distributions satisfy the approximate tensorisation of the entropy. We conjecture that the bounds we have here are optimal for $G(n,d/n)$. As corollary of our analysis for the Hard-core model, we also get bounds on the mixing time of the Glauber dynamics for the Monomer-dimer model on $G(n,d/n)$. The bounds we get for this model are slightly better than those we have for the Hard-core model

We present novel results for fast mixing of Glauber dynamics using the newly introduced and powerful Spectral Independence method from [Anari, Liu, Oveis-Gharan: FOCS 2020]. In our results, the parameters of the Gibbs distribution are expressed in terms of the spectral radius of the adjacency matrix of $G$, or that of the Hashimoto non-backtracking matrix. The analysis relies on new techniques that we introduce to bound the maximum eigenvalue of the pairwise influence matrix $\mathcal{I}^{\Lambda,\tau}_{G}$ for the two spin Gibbs distribution $\mu$. There is a common framework that underlies these techniques which we call the topological method. The idea is to systematically exploit the well-known connections between $\mathcal{I}^{\Lambda,\tau}_{G}$ and the topological construction called tree of self-avoiding walks. Our approach is novel and gives new insights to the problem of establishing spectral independence for Gibbs distributions. More importantly, it allows us to derive new -- improved -- rapid mixing bounds for Glauber dynamics on distributions such as the Hard-core model and the Ising model for graphs that the spectral radius is smaller than the maximum degree.

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 model defined on independent sets of an input graph where the independent sets are weighted by a parameter $\lambda>0$. For constant $\Delta$, previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree $\Delta$ when $\lambda< \lambda_c(\Delta)$. The threshold $\lambda_c(\Delta)$ is the critical point for the phase transition for uniqueness/non-uniqueness on the infinite $\Delta$-regular trees. Sly (2010) showed that there is no FPRAS, unless NP=RP, when $\lambda>\lambda_c(\Delta)$. 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 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$, 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 constant $\Delta$ whereas our work applies for all $\Delta \geq \Delta_0$. We utilize loopy BP (belief propagation), a widely-used inference algorithm. 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 converges, after a short burn-in period, 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)$.

Let $G=G(n,m)$ be a random graph whose average degree $d=2m/n$ is below the $k$-colorability threshold. If we sample a $k$-coloring $\sigma$ of $G$ uniformly at random, what can we say about the correlations between the colors assigned to vertices that are far apart? According to a prediction from statistical physics, for average degrees below the so-called {\em condensation threshold} $d_c(k)$, the colors assigned to far away vertices are asymptotically independent [Krzakala et al.: Proc. National Academy of Sciences 2007]. We prove this conjecture for $k$ exceeding a certain constant $k_0$. More generally, we investigate the joint distribution of the $k$-colorings that $\sigma$ induces locally on the bounded-depth neighborhoods of any fixed number of vertices. In addition, we point out an implication on the reconstruction problem.

Let $k\geq3$ be a fixed integer and let $Z_k(G)$ be the number of $k$-colourings of the graph $G$. For certain values of the average degree, the random variable $Z_k(G(n,m))$ is known to be concentrated in the sense that $\frac1n(\ln Z_k(G(n,m))-\ln E[Z_k(G(n,m))])$ converges to $0$ in probability [Achlioptas and Coja-Oghlan: FOCS 2008]. In the present paper we prove a significantly stronger concentration result. Namely, we show that for a wide range of average degrees, $\frac1\omega(\ln Z_k(G(n,m))-\ln E[Z_k(G(n,m))])$ converges to $0$ in probability for any diverging function $\omega=\omega(n)\to\infty$. For $k$ exceeding a certain constant $k_0$ this result covers all average degrees up to the so-called condensation phase transition, and this is best possible. As an application, we show that the experiment of choosing a $k$-colouring of the random graph $G(n,m)$ uniformly at random is contiguous with respect to the so-called "planted model".

Let G(n,d) be the random d-regular graph on n vertices. For any integer k exceeding a certain constant k_0 we identify a number d_{k-col} such that G(n,d) is k-colorable w.h.p. if dd_{k-col}.

Sampling from Gibbs distribution is a central 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 \lambda when the underlying graph is an instance of Erdos-Renyi 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 \lambda 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 somehow diminishes. However, devising such a construction of blocks is a highly non trivial task. We develop for a first time a weighting schema for the paths of the underlying graph. Vertices which belong to "light" paths, only, can be placed at the boundaries of the blocks. Then the tree-like local structure of G(n,d/n) allows the construction of simple structured blocks.

The broadcasting models on a d-ary tree T arise in many contexts such as biology, information theory, statistical physics and computer science. We consider the k-colouring model, i.e. the root of T is assigned an arbitrary colour and, conditional on this assignment, we take a random colouring of T. A basic question here is whether the information of the assignment at the root affects the distribution of the colourings at the leaves. This is the so-called reconstruction/non-reconstruction problem. It is well known that d/ln d is a threshold function for this problem, i.e. * if k \geq (1+\eps)d/ln d, then the colouring of the root has a vanishing effect on the distribution of the colourings at the leaves, as the height of the tree grows * if $k\leq (1-\eps)d/ln d, then the colouring of the root biases the distribution of the colouring of the leaves regardless of the height of the tree. There is no apparent combinatorial reason why such a result should be true. When k\geq (1+\eps)d/ ln d, the threshold implies the following: We can couple two broadcasting processes that assign the root different colours such that the probability of having disagreement at the leaves reduces with their distance from the root. It is natural to perceive such coupling as a mapping from the colouring of the first broadcasting process to the colouring of the second one. Here, we study how can we have such a mapping "combinatorially". Devising a mapping where the disagreements vanish as we move away from the root turns out to be a non-trivial task to accomplish for any k \leq d. In this work we obtain a coupling which has the aforementioned property for any k>3d/ln d, i.e. much smaller than d. Interestingly enough, the decisions that we make in the coupling are local. We relate our result to sampling k-colourings of sparse random graphs, with expected degree d and k