Theory seminar this friday: Dimitris Achlioptas

From: Anna Karlin (karlin@cs.washington.edu)
Date: Wed Mar 31 2004 - 15:13:36 PST

  • Next message: Anna Karlin: "reminder: first theory seminar today 11:30am in EE1 045"

    We have a great opening talk for theory seminar 590Z this quarter; Friday at 11:30am in EE1 045

    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


  • Next message: Anna Karlin: "reminder: first theory seminar today 11:30am in EE1 045"

    This archive was generated by hypermail 2.1.6 : Wed Mar 31 2004 - 15:13:55 PST