ARC Colloquium: Ricardo Restrepo, Institute of Mathematics, Universidad de Antioquia

Title: Frozenness threshold in random CSPs

Abstract:

Freezing is a key part of the clustering phenomenon that is hypothesized by non-rigorous techniques from statistical physics. Indeed, it has been shown that for different kinds of random CSPs (coloring, SAT, xor-sat, and other families), if the constraint-density of a random CSP, F, in our family is greater than r_f then for almost every solution of F, a linear number of variables are frozen, meaning that their colours cannot be changed by a sequence of alterations in which we change o(n) variables at a time, always switching to another solution. If the constraint-density is less than r_f, then almost every solution has o(n) frozen variables.

 The understanding of clustering has led to the development of advanced heuristics such as Survey Propagation. It has been suggested that the freezing threshold is a precise algorithmic barrier.  There is reason to believe that for densities below r_f the random CSPs can be solved using very simple algorithms, while for densities above r_f one requires more sophisticated techniques in order to deal with frozen clusters.

 In this talk we will explain the current state of the art regarding the appearance of frozenness in random CSPs and we'll explain some of the tecniques used to analitically study such a phenomena.

Event Details

Date/Time:

  • Monday, April 1, 2013
    1:30 pm - 2:30 pm
Location: Klaus 1116W

For More Information Contact