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

Given a collection of events in a probability space it is often desirable to bound from below the probability of arbitrary intersections of them, in the presence of negative correlation, i.e., when the occurrence of each event may make the occurrence of certain other events less likely. A classic tool for modelling negative correlation is a “dependency” graph, whose vertices correspond to events and whose edges indicate dependence. When the dependency graph is sufficiently sparse, the famous Lovász Local Lemma gives an explicit, strictly positive lower bound for the probability of every intersection. Here we extend the dependency graph setting from probabilities of intersections of events to arbitrary supermodular functions and derive corresponding explicit, strictly positive lower bounds.

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.

The celebrated Four Functions Theorem of Ahlswede and Daykin is a functional correlation inequality on distributive lattices with myriad applications. Ruozzi proved a variant of the inequality and used it to settle a major conjecture in the area of graphical models. We prove a new functional correlation inequality in the same vein which simplifies the proof of both the Four Functions Theorem and of Ruozzi’s inequality and suggests a unified picture for correlation inequalities on distributive lattices.

The independent set polynomial of a graph has one variable for each vertex and one monomial for each independent set, comprising the product of the corresponding variables. Given a graph G on n vertices and a vector p ∈ [0,1)ⁿ, a central problem in statistical mechanics is determining whether the independent set polynomial of G is non-vanishing in the polydisk of p, i.e., whether |Z_G(x)| > 0 for every x ∈ ℂⁿ such that |x_i| ≤ p_i. Remarkably, when this holds, Z_G(-p) is a lower bound for the avoidance probability when G is a dependency graph for n events whose probabilities form vector p. A local sufficient condition for |Z_G| > 0 in the polydisk of p is the Lovász Local Lemma (LLL). In this work we derive several new results on the efficient evaluation and bounding of Z_G. Our starting point is a monotone mapping from subgraphs of G to truncations of the tree of self-avoiding walks of G. Using this mapping our first result is a local upper bound for Z(-p), similar in spirit to the local lower bound for Z(-p) provided by the LLL. Next, using this mapping, we show that when G is chordal, Z_G can be computed exactly and in linear time on the entire complex plane, implying perfect sampling for the hard-core model on chordal graphs. We also revisit the task of bounding Z(-p) from below, i.e., the LLL setting, and derive four new lower bounds of increasing sophistication. Already our simplest (and weakest) bound yields a strict improvement of the famous asymmetric LLL, i.e., a strict relaxation of the inequalities of the asymmetric LLL without any further assumptions. This new asymmetric local lemma is sharp enough to recover Shearer’s optimal bound in terms of the maximum degree Δ(G). We also apply our more sophisticated bounds to estimate the zero-free region of the hard-core model on the triangular lattice (hard hexagons model).