Abstract: For many random Constraint Satisfaction Problems, by now, we have asymptotically tight estimates of
the largest constraint density for which they have solutions. At the same time, all known polynomial-time algorithms
for many of these problems already completely fail to find 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 already achieve this goal. Given the simplicity of those algorithms, one
would expect there is a lot of room for improvement. Yet, to date, no algorithm is known that uses (2 - o)÷ 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 believe it is 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, the set of k-colorings looks like a giant ball for k ? 2÷, but
like an error-correcting code for k ? (2 - o)÷. We prove that a completely analogous phase transition also occurs both in random k-SAT and in random hypergraph 2-coloring. And that for each problem, its location corresponds precisely with the point were all known polynomial-time algorithms fail. To prove our results we develop a general technique that allows us to prove rigorously much of the celebrated 1-step Replica-Symmetry-Breaking hypothesis
of statistical physics for random CSPs.
Abstract: For various random constraint satisfaction problems there is a significant gap between the largest constraint density
for which solutions exist and the largest density for which any polynomial time algorithm is known to find
solutions. Examples of this phenomenon include random k-SAT, random graph coloring, and a number of other
random Constraint Satisfaction Problems. To understand this gap, we study the structure of the solution space of
random k-SAT (i.e., the set of all satisfying assignments viewed as a subgraph of the Hamming cube). We prove
that for densities well below the satisfiability threshold, the solution space decomposes into an exponential number
of connected components and give quantitative bounds for the diameter, volume and number.
Abstract: For various random constraint satisfaction problems there is a significant gap between
the largest constraint density for which solutions exist and the largest density for which any polynomial
time algorithm is known to find solutions. Examples of this phenomenon include random
k-SAT, random graph coloring, and a number of other random constraint satisfaction problems. To
understand this gap, we study the structure of the solution space of random k-SAT (i.e., the set of
all satisfying assignments viewed as a subgraph of the Hamming cube). We prove that for densities
well below the satisfiability threshold, the solution space decomposes into an exponential number of
connected components and give quantitative bounds for the diameter, volume, and numb
Abstract: In recent years there has been signi1cant interest in the study of random k-SAT formulae. For
a given set of n Boolean variables, let Bk denote the set of all possible disjunctions of k distinct,
non-complementary literals from its variables (k-clauses). A random k-SAT formula Fk (n;m) is
formed by selectinguniformly and independently m clauses from Bk and takingtheir conjunction.
Motivated by insights from statistical mechanics that suggest a possible relationship between the
?order? of phase transitions and computational complexity, Monasson and Zecchina (Phys. Rev.
E 56(2) (1997) 1357) proposed the random (2+p)-SAT model: for a given p ¸ [0; 1], a random
(2 + p)-SAT formula, F2+p(n;m), has m randomly chosen clauses over n variables, where pm
clauses are chosen from B3 and (1 − p)m from B2. Usingthe heuristic ?replica method? of
statistical mechanics, Monasson and Zecchina gave a number of non-rigorous predictions on the
behavior of random (2 + p)-SAT formulae. In this paper we give the 1rst rigorous results for
random (2 + p)-SAT, includingthe followingsurprisingfact: for p 6 2=5, with probability
1 − o(1), a random (2 + p)-SAT formula is satis1able i@ its 2-SAT subformula is satis1able.
That is, for p 6 2=5, random (2 + p)-SAT behaves like random 2-SAT.
Abstract: One of the most challenging problems in probability and complexity theory is
to establish and determine the satisfiability threshold, or phase transition, for
random k-SAT instances: Boolean formulas consisting of clauses with exactly k
literals. As the previous part of the volume has explored, empirical observations
suggest that there exists a critical ratio of the number of clauses to the number
of variables, such that almost all randomly generated formulas with a higher
ratio are unsatisfiable while almost all randomly generated formulas with a lower
ratio are satisfiable. The statement that such a crossover point really exists is
called the satisfiability threshold conjecture. Experiments hint at such a direction,
but as far as theoretical work is concerned, progress has been difficult. In an
important advance, Friedgut [23] showed that the phase transition is a sharp one,
though without proving that it takes place at a “fixed” ratio for large formulas.
Otherwise, rigorous proofs have focused on providing successively better upper
and lower bounds for the value of the (conjectured) threshold. In this chapter, our