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

Event Details
  • Date/Time:
    • Monday April 1, 2013
      1:30 pm - 2:30 pm
  • Location: Klaus 1116W
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:


Summary Sentence: Ricardo Restrepo presents a talk as part of the ARC Colloquium series.

Full Summary: No summary paragraph submitted.

Title: Frozenness threshold in random CSPs


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.

Additional Information

In Campus Calendar

School of Computer Science, ARC

Invited Audience
Undergraduate students, Faculty/Staff, Graduate students
No keywords were submitted.
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Mar 28, 2013 - 6:04am
  • Last Updated: Apr 13, 2017 - 5:24pm