We analyse the performance of Belief Propagation Guided Decimation, a physics-inspired message passing algorithm, on the random $k$-XORSAT problem. Specifically, we derive an explicit threshold up to which the algorithm succeeds with a strictly positive probability $Ω(1)$ that we compute explicitly, but beyond which the algorithm with high probability fails to find a satisfying assignment. In addition, we analyse a thought experiment called the decimation process for which we identify a (non-) reconstruction and a condensation phase transition. The main results of the present work confirm physics predictions from [RTS: J. Stat. Mech. 2009] that link the phase transitions of the decimation process with the performance of the algorithm, and improve over partial results from a recent article [Yung: Proc. ICALP 2024].

Abstract. In an influential article, Papadimitriou [ On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pp. 163–169] proved that a local search algorithm called WalkSAT finds a satisfying assignment of a satisfiable 2-CNF with [Formula: see text] variables in [Formula: see text] expected time. Variants of the WalkSAT algorithm have become a mainstay of practical SAT solving (see, e.g., [Hoos and Stützle, J. Autom. Reason., 24 (2000), pp. 421–481]). In the present article, we analyze the expected running time of WalkSAT on random 2-SAT instances. Answering a question raised by Alekhnovich and Ben-Sasson [ SIAM J. Comput., 36 (2007) pp. 1248–1263], we show that WalkSAT runs in linear expected time for all clause/variable densities up to the random 2-SAT satisfiability threshold.

We prove that throughout the satisfiable phase, the logarithm of the number of satisfying assignments of a random 2-SAT formula satisfies a central limit theorem. This implies that the log of the number of satisfying assignments exhibits fluctuations of order √n, with n the number of variables. The formula for the variance can be evaluated effectively. By contrast, for numerous other random constraint satisfaction problems the typical fluctuations of the logarithm of the number of solutions are bounded throughout all or most of the satisfiable regime.

We derive a sufficient condition for a sparse random matrix with given numbers of non-zero entries in the rows and columns having full row rank. The result covers both matrices over finite fields with independent non-zero entries and $\{0,1\}$-matrices over the rationals. The sufficient condition is generally necessary as well.

We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease within a population of size n, based on the outcomes of pooled tests which return positive whenever there is at least one infected individual in the tested group. We consider two different simple random procedures for assigning individuals to tests: the constant-column design and Bernoulli design. Our first set of results concerns the fundamental statistical limits. For the constant-column design, we give a new information-theoretic lower bound which implies that the proportion of correctly identifiable infected individuals undergoes a sharp “all-or-nothing” phase transition when the number of tests crosses a particular threshold. For the Bernoulli design, we determine the precise number of tests required to solve the associated detection problem (where the goal is to distinguish between a group testing instance and pure noise), improving both the upper and lower bounds of Truong, Aldridge, and Scarlett (2020). For both group testing models, we also study the power of computationally efficient (polynomial-time) inference procedures. We determine the precise number of tests required for the class of low-degree polynomial algorithms to solve the detection problem. This provides evidence for an inherent computational-statistical gap in both the detection and recovery problems at small sparsity levels. Notably, our evidence is contrary to that of Iliopoulos and Zadik (2021), who predicted the absence of a computational-statistical gap in the Bernoulli design.

We study the performance of Markov chains for the $q$-state ferromagnetic Potts model on random regular graphs. It is conjectured that their performance is dictated by metastability phenomena, i.e., the presence of "phases" (clusters) in the sample space where Markov chains with local update rules, such as the Glauber dynamics, are bound to take exponential time to escape. The phases that are believed to drive these metastability phenomena in the case of the Potts model emerge as local, rather than global, maxima of the so-called Bethe functional, and previous approaches of analysing these phases based on optimisation arguments fall short of the task. Our first contribution is to detail the emergence of the metastable phases for the $q$-state Potts model on the $d$-regular random graph for all integers $q,d\geq 3$, and establish that for an interval of temperatures, which is delineated by the uniqueness and a broadcasting threshold on the $d$-regular tree, the two phases coexist. The proofs are based on a conceptual connection between spatial properties and the structure of the Potts distribution on the random regular graph, rather than complicated moment calculations. Based on this new structural understanding of the model, we obtain various algorithmic consequences. We first complement recent fast mixing results for Glauber dynamics by Blanca and Gheissari below the uniqueness threshold, showing an exponential lower bound on the mixing time above the uniqueness threshold. Then, we obtain tight results even for the non-local Swendsen-Wang chain, where we establish slow mixing/metastability for the whole interval of temperatures where the chain is conjectured to mix slowly on the random regular graph. The key is to bound the conductance of the chains using a random graph "planting" argument combined with delicate bounds on random-graph percolation.

We study the Consensus problem among $n$ agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called $j$-Majority: when activated, every agent samples $j$ other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: $(j+1)$-Majority (for $j > 1$) converges stochastically faster than $j$-Majority for any initial opinion configuration. In our analysis we use Strassen's Theorem to prove the existence of a coupling. This gives an affirmative answer for the case of two opinions to an open question asked by Berenbrink et al. [2017].

The last decade witnessed several pivotal results on random inference problems where the aim is to learn a hidden ground truth from indirect randomised observations; much of this research has been guided by statistical physics intuition. Prominent examples include the stochastic block model, low-density parity check codes or compressed sensing. In all random inference problems studied so far the posterior distribution of the ground truth given the observations appears to enjoy a key property called “strong replica symmetry”. This means that the overlap of the posterior distribution with the ground truth (basically the number of bits that can be learned correctly) concentrates on a deterministic value. Whether this is generally true has been an open question. In this paper we discover an example of an inference problem based on a very simple random matrix over that fails to exhibit strong replica symmetry. Beyond its impact on random inference problems, the random matrix model, reminiscent of the binomial Erdős-Rényi random graph, gives rise to a natural random constraint satisfaction problem related to the intensely studied random k-XORSAT problem.

The group testing problem asks for efficient pooling schemes and inference algorithms that allow to screen moderately large numbers of samples for rare infections. The goal is to accurately identify the infected individuals while minimizing the number of tests. We propose the novel adaptive pooling scheme adaptive Belief Propagation (ABP) that acknowledges practical limitations such as limited pooling sizes and noisy tests that may give imperfect answers. We demonstrate that the accuracy of ABP surpasses that of individual testing despite using few overall tests. The new design comes with Belief Propagation as an efficient inference algorithm. While the development of ABP is guided by mathematical analyses and asymptotic insights, we conduct an experimental study to obtain results on practical population sizes.

The Ising antiferromagnet is an important statistical physics model with close connections to the Max Cut problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry breaking phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the Max Cut of random regular graphs predicted by Zdeborová and Boettcher [ J. Stat. Mech., 2010 (2010), P02020]. As an application we prove that the information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten--Stigum bound.

Random factor graphs provide a powerful framework for the study of inference problems such as decoding problems or the stochastic block model. Information-theoretically the key quantity of interest is the mutual information between the observed factor graph and the underlying ground truth around which the factor graph was created; in the stochastic block model, this would be the planted partition. The mutual information gauges whether and how well the ground truth can be inferred from the observable data. For a very general model of random factor graphs we verify a formula for the mutual information predicted by physics techniques. As an application we prove a conjecture about low-density generator matrix codes from [Montanari: IEEE Transactions on Information Theory 2005]. Further applications include phase transitions of the stochastic block model and the mixed $k$-spin model from physics.

Guided by the theory of graph limits, we investigate a variant of the cut metric for limit objects of sequences of discrete probability distributions. Apart from establishing basic results, we introduce a natural operation called pinning on the space of limit objects and show how this operation yields a canonical cut metric approximation to a given probability distribution akin to the weak regularity lemma for graphons. We also establish the cut metric continuity of basic operations such as taking product measures.

In the group testing problem, which goes back to the work of Dorfman (1943), we aim to identify a small set of $k\sim n^\theta$ infected individuals out of a population size $n$, $0<\theta<1$.We avail ourselves to a test procedure that can test a group of individuals, with the test returning a positive result iff at least one individual in the group is infected. All tests are conducted in parallel. The aim is to devise a test design with as few tests as possible so that the infected individuals can be identified with high probability. We establish an explicit sharp information-theoretic/algorithmic phase transition $m_{inf}$, showing that with more than $\minf$ tests the infected individuals can be identified in polynomial time, while this is impossible with fewer tests. In addition, we obtain an optimal two-stage adaptive group testing scheme. These results resolve problems prominently posed in [Aldridge et al. 2019, Johnson et al. 2018, Mézard and Toninelli 2011].

We determine the rank of a random matrix A over an arbitrary field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes. This formula vindicates a conjecture of Lelarge [Proc. IEEE Information Theory Workshop 2013]. The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that likely diminishes the number of short linear relations.

In the group testing problem we aim to identify a small number of infected individuals within a large population. We avail ourselves to a procedure that can test a group of multiple individuals, with the test result coming out positive iff at least one individual in the group is infected. With all tests conducted in parallel, what is the least number of tests required to identify the status of all individuals? In a recent test design [Aldridge et al. 2016] the individuals are assigned to test groups randomly with replacement, with every individual joining an almost equal number of groups. We pinpoint the sharp threshold for the number of tests required in this randomised design so that it is information-theoretically possible to infer the infection status of every individual. Moreover, we analyse two efficient inference algorithms. These results settle conjectures from [Aldridge et al. 2014, Johnson et al. 2019].

In the group testing problem we aim to identify a small number of infected individuals within a large population. We avail ourselves to a procedure that can test a group of multiple individuals, with the test result coming out positive iff at least one individual in the group is infected. With all tests conducted in parallel, what is the least number of tests required to identify the status of all individuals? In a recent test design [Aldridge et al. 2016] the individuals are assigned to test groups randomly, with every individual joining an equal number of groups. We pinpoint the sharp threshold for the number of tests required in this randomised design so that it is information-theoretically possible to infer the infection status of every individual. Moreover, we analyse two efficient inference algorithms. These results settle conjectures from [Aldridge et al. 2014, Johnson et al. 2019].

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].

Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we establish a formula for the mutual information in statistical inference problems induced by random graphs. This general result implies the conjecture on the information-theoretic threshold in the disassortative stochastic block model [Decelle et al.: Phys. Rev. E (2011)] and allows us to pinpoint the exact condensation phase transition in random constraint satisfaction problems such as random graph coloring, thereby proving a conjecture from [Krzakala et al.: PNAS (2007)]. As a further application we establish the formula for the mutual information in Low-Density Generator Matrix codes as conjectured in [Montanari: IEEE Transactions on Information Theory (2005)]. The proofs provide a conceptual underpinning of the replica symmetric variant of the cavity method, and we expect that the approach will find many future applications.

Let Φ be a uniformly distributed random k -SAT formula with n variables and m clauses. Nonconstructive arguments show that Φ is satisfiable for clause/variable ratios m / n ⩽ r k − SAT ∼ 2 k ln 2 with high probability. Yet no efficient algorithm is known to find a satisfying assignment beyond m / n ∼ 2 k ln ( k )/ k with a nonvanishing probability. On the basis of deep but nonrigorous statistical mechanics ideas, a message passing algorithm called Belief Propagation Guided Decimation has been put forward (Mézard, Parisi, Zecchina: Science 2002; Braunstein, Mézard, Zecchina: Random Struc. Algorithm 2005). Experiments suggested that the algorithm might succeed for densities very close to r k − SAT for k = 3, 4, 5 (Kroc, Sabharwal, Selman: SAC 2009). Furnishing the first rigorous analysis of this algorithm on a nontrivial input distribution, in the present article we show that Belief Propagation Guided Decimation fails to solve random k -SAT formulas already for m / n = O (2 k / k ), almost a factor of k below the satisfiability threshold r k − SAT . Indeed, the proof refutes a key hypothesis on which Belief Propagation Guided Decimation hinges for such m / n .

Partly on the basis of heuristic arguments from physics, it has been suggested that the performance of certain types of algorithms on random $k$-SAT formulas is linked to phase transitions that affect the geometry of the set of satisfying assignments. But, beyond intuition, there has been scant rigorous evidence that “practical” algorithms are affected by these phase transitions. In this paper we prove that Walksat, a popular randomized satisfiability algorithm, fails on random $k$-SAT formulas not very far above clause/variable density, where the set of satisfying assignments shatters into tiny, well-separated clusters. Specifically, we prove that Walksat is ineffective with high probability (w.h.p.) if $m/n>c2^k\ln^2k/k$, where $m$ is the number of clauses, $n$ is the number of variables, and $c>0$ is an absolute constant. By comparison, Walksat is known to find satisfying assignments in linear time w.h.p. if $m/n 0$ [A. Coja-Oghlan and A. Frieze, SIAM J. Comput., 43 (2014), pp. 1456--1485].

Much of the recent work on random constraint satisfaction problems has been inspired by ingenious but non-rigorous approaches from physics. The physics predictions typically come in the form of distributional fixed point problems that are intended to mimic Belief Propagation, a message passing algorithm, applied to the random CSP. In this paper we propose a novel method for harnessing Belief Propagation directly to obtain a rigorous proof of such a prediction, namely the existence and location of a condensation phase transition in the random regular $k$-SAT model.

Gibbs measures induced by random factor graphs play a prominent role in computer science, combinatorics and physics. A key problem is to calculate the typical value of the partition function. According to the "replica symmetric cavity method", a heuristic that rests on non-rigorous considerations from statistical mechanics, in many cases this problem can be tackled by way of maximising a functional called the "Bethe free energy". In this paper we prove that the Bethe free energy upper-bounds the partition function in a broad class of models. Additionally, we provide a sufficient condition for this upper bound to be tight.

In the planted bisection model a random graph G(n,p_+,p_-) with n vertices is created by partitioning the vertices randomly into two classes of equal size (up to plus or minus 1). Any two vertices that belong to the same class are linked by an edge with probability p_+ and any two that belong to different classes with probability (p_-) <(p_+) independently. The planted bisection model has been used extensively to benchmark graph partitioning algorithms. If (p_+)=2(d_+)/n and (p_-)=2(d_-)/n for numbers 0 <= (d_-) <(d_+) that remain fixed as n tends to infinity, then with high probability the "planted" bisection (the one used to construct the graph) will not be a minimum bisection. In this paper we derive an asymptotic formula for the minimum bisection width under the assumption that (d_+)-(d_-) > c * sqrt((d_+)ln(d_+)) for a certain constant c>0.

We consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least r active neighbors, where r > 1 is the activation threshold. A contagious set is a set whose activation results with the entire graph being active. Given a graph G, let m(G, r) be the minimal size of a contagious set. It is known that for every d-regular or nearly d-regular graph on n vertices, . We consider such graphs that additionally have expansion properties, parameterized by the spectral gap and/or the girth of the graphs. The general flavor of our results is that sufficiently strong expansion properties imply that (and more generally, . In addition, we demonstrate that rather weak assumptions on the girth and/or the spectral gap suffice in order to imply that . For example, we show this for graphs of girth at least 7, and for graphs with λ(G) < (1 − ε)d, provided the graph has no 4-cycles. Our results are algorithmic, entailing simple and effcient algorithms for selecting contagious sets.

Based on a non-rigorous formalism called the "cavity method", physicists have put forward intriguing predictions on phase transitions in discrete structures. One of the most remarkable ones is that in problems such as random k-SAT or random graph k-coloring, very shortly before the threshold for the existence of solutions there occurs another phase transition called condensation [Krzakala et al., PNAS 2007]. The existence of this phase transition appears to be intimately related to the difficulty of proving precise results on, e.g., the k-colorability threshold as well as to the performance of message passing algorithms. In random graph k-coloring, there is a precise conjecture as to the location of the condensation phase transition in terms of a distributional fixed point problem. In this paper we prove this conjecture for k exceeding a certain constant k0.

Since the early 2000s physicists have developed an ingenious but non-rigorous formalism called the cavity method to put forward precise conjectures as to the phase transitions in random constraint satisfaction problems ("CSPs"). The cavity method comes in two versions: the simpler replica symmetric variant, and the more intricate 1-step replica symmetry breaking ("1RSB") version. While typically the former only gives upper and lower bounds, the latter is conjectured to yield precise results in many cases. By now, there are a number of examples where the replica symmetric bounds have been verified rigorously. However, verifications of 1RSB predictions are scarce. Perhaps the most prominent challenge in this context is that of pinning down the random k-SAT threshold rk--SAT. Here we prove that rk--SAT = 2k ln 2--1/2 (1 + ln 2) + ok(1), which matches the 1RSB prediction up to the ok(1) error term. The proof directly employs ideas from the 1RSB cavity method, such as the notion of covers (relaxed satisfying assignments) and bits of the Survey Propagation calculations. The best previous lower bound was rk--SAT ≥ 2k ln 2--3/2 ln 2 + ok(1), matching the replica symmetric lower bound asymptotically [Coja-Oghlan, Panagiotou: STOC 2013].

Let $\mathbf{\Phi}$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. We prove that the \tt Walksat algorithm from Papadimitriou [On selecting a satisfying truth assignment, in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1991, pp. 163--169] and Schöning [A probabilistic algorithm for $k$-SAT and constraint satisfaction problems, in Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Soc., Los Alamitos, CA, 1999, pp. 410--414] finds a satisfying assignment of $\mathbf{\Phi}$ in polynomial time with high probability if $m/n\leq\rho\cdot2^k/k$ for a certain constant $\rho>0$. This is an improvement by a factor of $\Theta(k)$ over the best previous analysis of \tt Walksat from Coja-Oghlan et al. [On smoothed $k$-CNF formulas and the Walksat algorithm, in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia, 2009, pp. 451--460].

In this paper we establish a substantially improved lower bound on the k-color ability threshold of the random graph G(n, m) with n vertices and m edges. The new lower bound is ≈ 1.39 less than the 2k ln (k)-ln (k) first-moment upper bound (and approximately 0.39 less than the 2k ln (k) - ln(k) - 1 physics conjecture). By comparison, the best previous bounds left a gap of about 2+ln(k), unbounded in terms of the number of colors [Achlioptas, Naor: STOC 2004]. Furthermore, we prove that, in a precise sense, our lower bound marks the so-called condensation phase transition predicted on the basis of physics arguments [Krzkala et al.: PNAS 2007]. Our proof technique is a novel approach to the second moment method, inspired by physics conjectures on the geometry of the set of k-colorings of the random graph.

Random k-SAT is the single most intensely studied example of a random constraint satisfaction problem. But despite substantial progress over the past decade, the threshold for the existence of satisfying assignments is not known precisely for any k≥3. The best current results, based on the second moment method, yield upper and lower bounds that differ by an additive k ⋅ {ln2}/2, a term that is unbounded in k (Achlioptas, Peres: STOC 2003). The basic reason for this gap is the inherent asymmetry of the Boolean values 'true' and 'false' in contrast to the perfect symmetry, e.g., among the various colors in a graph coloring problem. Here we develop a new asymmetric second moment method that allows us to tackle this issue head on for the first time in the theory of random CSPs. This technique enables us to compute the k-SAT threshold up to an additive ln2-1/2+O(1/k) ~0.19. Independently of the rigorous work, physicists have developed a sophisticated but non-rigorous technique called the "cavity method" for the study of random CSPs (Mezard, Parisi, Zecchina: Science~2002). Our result matches the best bound that can be obtained from the so-called "replica symmetric" version of the cavity method, and indeed our proof directly harnesses parts of the physics calculations.

For many random constraint satisfaction problems such as random satisfiability or random graph or hypergraph coloring, the best current estimates of the threshold for the existence of solutions are based on the first and the second moment method. However, in most cases these techniques do not yield matching upper and lower bounds. Sophisticated but non-rigorous arguments from statistical mechanics have ascribed this discrepancy to the existence of a phase transition called condensation that occurs shortly before the actual threshold for the existence of solutions and that affects the combinatorial nature of the problem (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborová: PNAS 2007). In this paper we prove for the first time that a condensation transition exists in a natural random CSP, namely in random hypergraph 2-coloring. Perhaps surprisingly, we find that the second moment method applied to the number of 2-colorings breaks down strictly before the condensation transition. Our proof also yields slightly improved bounds on the threshold for random hypergraph 2-colorability.

The best current estimates of the thresholds for the existence of solutions in random constraint satisfaction problems ('CSPs') mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. According to deep but non-rigorous arguments from statistical mechanics, this discrepancy is due to a change in the geometry of the set of solutions called condensation that occurs shortly before the actual threshold for the existence of solutions (Krzakala, Montanari, Ricci-Tersenghi, Semerjian, Zdeborova: PNAS~2007). To cope with condensation, physicists have developed a sophisticated but non-rigorous formalism called Survey Propagation (Me-zard, Parisi, Zecchina: Science 2002). This formalism yields precise conjectures on the threshold values of many random CSPs. Here we develop a new Survey Propagation inspired second moment method for the random k-NAESAT problem, which is one of the standard benchmark problems in the theory of random CSPs. This new technique allows us to overcome the barrier posed by condensation rigorously. We prove that the threshold for the existence of solutions in random k-NAESAT is 2k-1ln2-(ln/2 2+1/4)+εk, where |εk| ≤ 2-(1-ok(1))k, thereby verifying the statistical mechanics conjecture for this problem.

Let $\boldsymbol{\Phi}$ be a uniformly distributed random $k$-SAT formula with $n$ variables and $m$ clauses. Nonrigorous statistical mechanics ideas have inspired a message passing algorithm called belief propagation guided decimation for finding satisfying assignments of $\boldsymbol{\Phi}$. This algorithm can be viewed as an attempt at implementing a certain thought experiment that we call the decimation process. In this paper we identify a variety of phase transitions in the decimation process and link these phase transitions to the performance of the algorithm.

Let Φ be a uniformly distributed random k-SAT formula with n variables and m clauses. Non-constructive arguments show that Φ is satisfiable for clause/variable ratios m/n ≤ rk ∼ 2k ln 2 with high probability (Achlioptas, Moore: SICOMP 2006; Achlioptas, Peres: J. AMS 2004). Yet no efficient algorithm is know to find a satisfying assignment for densities as low as m/n ∼ rk · ln(k)/k with a non-vanishing probability. In fact, the density m/n ∼ rk · ln(k)/k seems to form a barrier for a broad class of local search algorithms (Achlioptas, Coja-Oghlan: FOCS 2008). On the basis of deep but non-rigorous statistical mechanics considerations, a message passing algorithm called belief propagation guided decimation for solving random k-SAT has been forward (Mézard, Parisi, Zecchina: Science 2002; Braunstein, Mézard, Zecchina: RSA 2005). Experiments suggest that the algorithm might succeed for densities very close to rk for k = 3, 4, 5 (Kroc, Sabharwal, Selman: SAC 2009). Furnishing the first rigorous analysis of belief propagation guided decimation on random k-SAT, the present paper shows that the algorithm fails to find a satisfying assignment already for m/n ≥ ρ · rk/k, for a constant ρ > 0 independent of k.

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.

We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to express how much a given graph “resembles” a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we introduce a concept of regularity that takes into account vertex weights, and show that if $G=(V,E)$ satisfies a certain boundedness condition, then G admits a regular partition. In addition, building on the work of Alon and Naor [Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, ACM, New York, 2004, pp. 72–80], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph G in polynomial time. As an application, we present a polynomial time approximation scheme for MAX CUT on (sparse) graphs without “dense spots.”

Let $\boldsymbol{\Phi}$ be a uniformly distributed random k-SAT formula with n variables and m clauses. We present a polynomial time algorithm that finds a satisfying assignment of $\boldsymbol{\Phi}$ with high probability for constraint densities $m/n<(1-\varepsilon_k)2^k\ln(k)/k$, where $\varepsilon_k\rightarrow0$. Previously no efficient algorithm was known to find satisfying assignments with a nonvanishing probability beyond $m/n=1.817\cdot2^k/k$ [A. Frieze and S. Suen, J. Algorithms, 20 (1996), pp. 312–355].

Let ${\bf A}$ be a $0/1$ matrix of size $m\times n$, and let p be the density of ${\bf A}$ (i.e., the number of ones divided by $m\cdot n$). We show that ${\bf A}$ can be approximated in the cut norm within $\varepsilon\cdot mnp$ by a sum of cut matrices (of rank 1), where the number of summands is independent of the size $m\cdot n$ of ${\bf A}$, provided that ${\bf A}$ satisfies a certain boundedness condition. This decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan [Combinatorica, 19 (1999), pp. 175–220] to sparse matrices. As an application, we obtain efficient $1-\varepsilon$ approximation algorithms for “bounded” instances of MAX CSP problems.

Let A be a 0/1 matrix of size m×n, and let p be the density of A (i.e., the number of ones divided by m · n). We show that A can be approximated in the cut norm within ∊ · mnp by a sum of cut matrices (of rank 1), where the number of summands is independent of the size m · n of A, provided that A satisfies a certain boundedness condition. The decomposition can be computed in polynomial time. This result extends the work of Frieze and Kannan (Combinatorica 1999) to sparse matrices. As an application, we obtain efficient 1 – ∊ approximation algorithms for “bounded” instances of Max CSP problems.

In this paper we study the model of ∊-smoothed k-CNF formulas. Starting from an arbitrary instance F with n variables and m = dn clauses, apply the ∊-smoothing operation of flipping the polarity of every literal in every clause independently at random with probability ∊. Keeping ∊ and k fixed, and letting the density d = m/n grow, it is rather easy to see that for d ≥ ∊−-kln 2, F becomes whp unsatisfiable after smoothing. We show that a lower density that behaves roughly like ∊−-k+1 suffices for this purpose. We also show that our bound on d is nearly best possible in the sense that there are k-CNF formulas F of slightly lower density that whp remain satisfiable after smoothing. One consequence of our proof is a new lower bound of Ω(2k/k2) on the density up to which Walksat solves random k-CNFs in polynomial time whp. We are not aware of any previous rigorous analysis showing that Walksat is successful at densities that are increasing as a function of k.

We consider the problem of recovering a planted partition such as a coloring, a small bisection, or a large cut in an (apart from that) random graph. In the last 30 years many algorithms for this problem have been developed that work provably well on various random graph models resembling the Erdős–Rényi model $G_{n,m}$. In these random graph models edges are distributed uniformly, and thus the degree distribution is very regular. By contrast, the recent theory of large networks shows that real-world networks frequently have a significantly different distribution of the edges and hence also a different degree distribution. Therefore, a variety of new types of random graphs have been introduced to capture these specific properties. One of the most popular models is characterized by a prescribed expected degree sequence. We study a natural variant of this model that features a planted partition. Our main result is that there is a polynomial time algorithm for recovering (a large part of) the planted partition in this model even in the sparse case, where the average degree is constant. In contrast to prior work, the input of the algorithm consists only of the graph, i.e., no further parameters of the model (such as the expected degree sequence) are revealed to the algorithm.

For many random constraint satisfaction problems, by now there exist asymptotically tight estimates of the largest constraint density for which solutions exist. At the same time, for many of these problems, all known polynomial-time algorithms stop finding solutions at much smaller densities. For example, it is well-known that it is easy to color a random graph using twice as many colors as its chromatic number. Indeed, some of the simplest possible coloring algorithms achieve this goal. Given the simplicity of those algorithms, one would expect room for improvement. Yet, to date, no algorithm is known that uses (2 - epsiv)chi colors, in spite of efforts by numerous researchers over the years. In view of the remarkable resilience of this factor of 2 against every algorithm hurled at it, we find it natural to inquire into its origin. We do so by analyzing the evolution of the set of k-colorings of a random graph, viewed as a subset of {1,...,k}n, as edges are added. We prove that the factor of 2 corresponds in a precise mathematical sense to a phase transition in the geometry of this set. Roughly speaking, we prove that the set of k-colorings looks like a giant ball for k ges 2chi, but like an error-correcting code for k les (2 - epsiv)chi. We also prove that an analogous phase transition occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each of these three problems, the location of the transition corresponds to the point where all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to establish rigorously much of the celebrated 1-step replica-symmetry-breaking hypothesis of statistical physics for random CSPs.