*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
