We connect the study of phase transitions in high-dimensional statistical inference to the study of threshold phenomena in random graphs. A major question in the study of the Erdős–Rényi random graph $G(n,p)$ is to understand the probability, as a function of $p$, that $G(n,p)$ contains a given subgraph $H=H_n$. This was studied for many specific examples of $H$, starting with classical work of Erdős and Rényi (1960). More recent work studies this question for general $H$, both in building a general theory of sharp versus coarse transitions (Friedgut and Bourgain 1999; Hatami, 2012) and in results on the location of the transition (Kahn and Kalai, 2007; Talagrand, 2010; Frankston, Kahn, Narayanan, Park, 2019; Park and Pham, 2022).In inference problems, one often studies the optimal accuracy of inference as a function of the amount of noise. In a variety of sparse recovery problems, an “all-or-nothing (AoN) phenomenon” has been observed: Informally, as the amount of noise is gradually increased, at some critical threshold the inference problem undergoes a sharp jump from near-perfect recovery to near-zero accuracy (Gamarnik and Zadik, 2017; Reeves, Xu, Zadik, 2021). We can regard AoN as the natural inference analogue of the sharp threshold phenomenon in random graphs. In contrast with the general theorydeveloped for sharp thresholds of random graph properties, the AoNphenomenon has only been studied so far in specific inference settings, anda general theory behind its appearance remains elusive.In this paper we study the general problem of inferring a graph $H=H_n$ planted in an Erdős–Rényi random graph, thus naturally connecting the two lines of research mentioned above. We show that questions of AoN are closely connected to first moment thresholds, and to a generalization of the so-called Kahn–Kalai expectation threshold that scans over subgraphs of $H$ of edge density at least $q$. In a variety of settings we characterize AoN, by showing that AoN occurs \emph{if and only if} this “generalized expectation threshold” is roughly constant in $q$. Our proofs combine techniques from random graph theory and Bayesian inference.

We study a family of Ising perceptron models with {0,1}-valued activation functions. This includes the classical half-space models, as well as some of the symmetric models considered in recent works. For each of these models we show that the free energy is self-averaging, there is a sharp threshold sequence, and the free energy is universal with respect to the disorder. A prior work of C. Xu (2019) used very different methods to show a sharp threshold sequence in the half-space Ising perceptron with Bernoulli disorder. Recent works of Perkins-Xu (2021) and Abbe-Li-Sly (2021) determined the sharp threshold and limiting free energy in a symmetric perceptron model. The results of this paper apply in more general settings, and are based on new “add one constraint” estimates extending Talagrand's estimates for the half-space model (1999, 2011). * The full version of the paper can be accessed at https://arxiv.org/abs/2204.03469.

We consider the Ising perceptron model with N spins and M = N*alpha patterns, with a general activation function U that is bounded above. For U bounded away from zero, or U a one-sided threshold function, it was shown by Talagrand (2000, 2011) that for small densities alpha, the free energy of the model converges in the large-N limit to the replica symmetric formula conjectured in the physics literature (Krauth–Mezard 1989, see also Gardner–Derrida 1988). We give a new proof of this result, which covers the more general class of all functions U that are bounded above and satisfy a certain variance bound. The proof uses the (first and second) moment method conditional on the approximate message passing iterates of the model. In order to deduce our main theorem, we also prove a new concentration result for the perceptron model in the case where U is not bounded away from zero.

I will describe recent progress in determination of asymptotic behavior in random constraint satisfaction problems, including the independent set problem on random graphs, random regular NAE-SAT, and random SAT. The results include sharp phase transitions and some understanding of solution geometry, particularly in the setting of the random regular NAE-SAT problem. In this lecture I will survey the physics heuristics, and explain how they lead to combinatorial models for the solution geometry, which form a basis of mathematical approaches to these problems. As time allows, I will discuss some of the mathematical techniques that have been introduced, particularly with regards to solving certain non-convex optimization problems that arise in moment method calculations.

For several models of random constraint satisfaction problems, it was conjectured by physicists and later proved that a sharp satisfiability transition occurs. In the unsatisfiable regime, it is natural to consider the problem of max-satisfiability: violating the least number of constraints. This is a combinatorial optimization problem on the random energy landscape defined by the problem instance. In the bounded density regime, a very precise estimate of the max-sat value was obtained by Achlioptas, Naor, and Peres (2007), but it is not sharp enough to indicate the nature of the energy landscape. Later work (Sen, 2016; Panchenko, 2016) shows that for very large but bounded density, the max-sat value approaches the mean-field (complete graph) limit: this is conjectured to have an "FRSB" structure where near-optimal configurations form clusters within clusters, in an ultrametric hierarchy of infinite depth inside the discrete cube. A stronger form of FRSB was shown in several recent works to have algorithmic implications (again, in complete graphs). Consequently we find it of interest to understand how the model transitions from 1RSB near the satisfiability threshold, to (conjecturally) FRSB at large density. In this paper we show that in the random regular NAE-SAT model, the 1RSB description breaks down by a certain threshold density that we estimate rather precisely. This is proved by an explicit perturbation in the 2RSB parameter space. The choice of perturbation is inspired by the "bug proliferation" mechanism proposed by physicists (Montanari and Ricci-Tersenghi, 2003; Krzakala, Pagnani, and Weigt, 2004), corresponding roughly to a percolation-like threshold for a subgraph of dependent variables.

We consider the Ising perceptron with gaussian disorder, which is equivalent to the discrete cube {−1,+1}N intersected by M random half-spaces. The perceptron’s capacity is the largest integer MN for which the intersection is nonempty. It is conjectured by Krauth and Mézard (1989) that the (random) ratio MN/N converges in probability to an explicit constant α⋆≐ 0.83. Kim and Roche (1998) proved the existence of a positive constant γ such that γ ≤ MN/N ≤ 1−γ with high probability; see also Talagrand (1999). In this paper we show that the Krauth–Mézard conjecture α⋆ is a lower bound with positive probability, under the condition that an explicit univariate function S(λ) is maximized at λ=0. Our proof is an application of the second moment method to a certain slice of perceptron configurations, as selected by the so-called TAP (Thouless, Anderson, and Palmer, 1977) or AMP (approximate message passing) iteration, whose scaling limit has been characterized by Bayati and Montanari (2011) and Bolthausen (2012). For verifying the condition on S(λ) we outline one approach, which is implemented in the current version using (nonrigorous) numerical integration packages. In a future version of this paper we intend to complete the verification by implementing a rigorous numerical method.

Recent work has made substantial progress in understanding the transitions of random constraint satisfaction problems (CSPs). In particular, for several of these models, the exact satisfiability threshold has been rigorously determined, confirming predictions from the statistical physics literature. Here we revisit one of these models, random regular NAE-SAT: knowing the satisfiability threshold, it is natural to study, in the satisfiable regime, the number of solutions in a typical instance. We prove here that these solutions have a well-defined free energy (limiting exponential growth rate), with explicit value matching the one-step replica symmetry breaking prediction. The proof develops new techniques for analyzing a certain "survey propagation model" associated to this problem. We believe that these methods may be applicable in a wide class of related problems.

We establish the satisfiability threshold for random k-SAT for all k ≥ k0. That is, there exists a limiting density αs(k) such that a random k-SAT formula of clause density α is with high probability satisfiable for α < αs, and unsatisfiable for α > αs. The satisfiability threshold αs is given explicitly by the one-step replica symmetry breaking (1SRB) prediction from statistical physics. We believe that our methods may apply to a range of random constraint satisfaction problems in the 1RSB class.

We consider the random regular k-nae-sat problem with n variables each appearing in exactly d clauses. For all k exceeding an absolute constant k0, we establish explicitly the satisfiability threshold d* ∈ d*(k). We prove that for d < d* the problem is satisfiable with high probability while for d > d* the problem is unsatisfiable with high probability. If the threshold d* lands exactly on an integer, we show that the problem is satisfiable with probability bounded away from both zero and one. This is the first result to locate the exact satisfiability threshold in a random constraint satisfaction problem exhibiting the condensation phenomenon identified by Krzakał a et al. (2007). Our proof verifies the onestep replica symmetry breaking formalism for this model. We expect our methods to be applicable to a broad range of random constraint satisfaction problems and combinatorial problems on random graphs.

The class of two-spin systems contains several important models, including random independent sets and the Ising model of statistical physics. We show that for both the hard-core (independent set) model and the anti-ferromagnetic Ising model with arbitrary external field, it is NP-hard to approximate the partition function or approximately sample from the model on regular graphs when the model has non-uniqueness on the corresponding regular tree. Together with results of Jerrum -- Sinclair, Weitz, and Sinclair -- Srivastava -- Thurley giving FPRAS's for all other two-spin systems except at the uniqueness threshold, this gives an almost complete classification of the computational complexity of two-spin systems on bounded-degree graphs. Our proof establishes that the normalized log-partition function of any two-spin system on bipartite locally tree-like graphs converges to a limiting ``free energy density'' which coincides with the (non-rigorous) Be the prediction of statistical physics. We use this result to characterize the local structure of two-spin systems on locally tree-like bipartite expander graphs, which then become the basic gadgets in a randomized reduction to approximate MAX-CUT. Our approach is novel in that it makes no use of the second moment method employed in previous works on these questions.