Abstract: For many random ConstraintSatisfactionProblems, 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 constraintsatisfactionproblems 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 ConstraintSatisfactionProblems. 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 constraintsatisfactionproblems 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 constraintsatisfactionproblems. 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 the last few years there has been a great amount of interest in Random ConstraintSatisfactionProblems, both from an experimental and a theoretical point of view. Quite intriguingly, experimental results
with various models for generating random CSP instances suggest that the probability of such problems having
a solution exhibits a ?threshold-like? behavior. In this spirit, some preliminary theoretical work has been done
in analyzing these models asymptotically, i.e., as the number of variables grows. In this paper we prove that,
contrary to beliefs based on experimental evidence, the models commonly used for generating random CSP
instances do not have an asymptotic threshold. In particular, we prove that asymptotically almost all instances
they generate are overconstrained, suffering from trivial, local inconsistencies. To complement this result we
present an alternative, single-parameter model for generating random CSP instances and prove that, unlike
current models, it exhibits non-trivial asymptotic behavior. Moreover, for this new model we derive explicit
bounds for the narrow region within which the probability of having a solution changes dramatically
