From: Anna Karlin (karlin@cs.washington.edu)
Date: Fri Apr 02 2004 - 10:27:44 PST
TITLE: Complexity in Random Structures: When, How and Why?
SPEAKER: Dimitris Achlioptas, MSR
ABSTRACT: Many NP-complete problems are easy for random inputs. For
example, in a random graph where every edge appears with probability 1/2
one can find a Hamiltonian cycle in linear expected time. On the other
hand, random instances of satisfiability and graph coloring appear to be
hard. Moreover, for each problem there appears to be a critical ratio of
constraints-to-variables around which the probability of solubility
drops rapidly from near 1 to near 0. Determining these thresholds and
understanding the behavior of algorithms in their vicinity has attracted
researchers in artificial intelligence, combinatorics, probability,
theoretical computer science, and statistical physics.
We study the solution-space geometry of random constraint satisfaction
problems by using a new version of the second moment method. In
particular, we determine the threshold for both random graph coloring
and random satisfiability up to second order terms. Our results also
shed light on the difficulties faced by algorithms trying to operate in
the thresholds' vicinity. Specifically, we give exponential lower bounds
for the running time of natural satisfiability algorithms at densities
significantly below the satisfiability threshold. Physicists have
recently predicted that around these same densities the structure of the
space of solutions changes dramatically. We present some evidence in
that direction motivated by ideas from belief-propagation decoding of
error-correcting codes.
Based on work with Paul Beame, Mike Molloy, Cris Moore, Assaf Naor,
Yuval Peres, and Jeremy Thorpe.
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Fri Apr 02 2004 - 10:28:06 PST