[Ml-stat-talks] Dimitris Achlioptas - today - Algorithmic Barriers from Phase Transitions

Ramon van Handel rvan at Princeton.EDU
Fri Mar 21 10:10:59 EDT 2014

Dear all,

A reminder that Dimitris Achlioptas gives the first Blackboard sessions 
today on Algorithmic Barriers from Phase Transitions (abstract is below). 
The blackboard sessions are intended to be tutorial style and no prior 
background of the area is required. This will be fantastic--don't miss it!

The location is Sherrerd Hall, Room 101.

The schedule is as follows (*today*, March 21, 2014):

10:30 AM - 12:00 PM: Morning session
12:00 PM - 1:30 PM:  Lunch break
1:30 PM  - 3:00 PM:  Afternoon session

All the best,  -- Ramon

TITLE: Algorithmic Barriers from Phase Transitions

ABSTRACT: The study of randomly generated Constraint Satisfaction Problems 
(CSPs) in Computer Science began about 25 years ago. From the outset, 
notions from statistical physics were invoked, primarily “phase 
transitions”. It took computer scientists and physicists about a decade 
after that point to figure out that “diluted mean-field spin glasses” are 
“random CSPs” (and vice versa). After that rather slow start, a very 
fruitful and exciting exchange of ideas between the two fields has been 
taking place, at an accelerating pace. Central to this exchange is the 
heuristic notion that symmetry breaking, by introducing long-range 
correlations, can create computational hardness. In these sessions I will 
survey our current understanding of this central point, discuss open 
problems, and some connections to problems in communication and machine 

SPEAKER BIO: Dimitris Achlioptas joined the Department of Computer Science 
of UC Santa Cruz in 2005 after being with Microsoft Research, Redmond from 
1998. In theory, his expertise lies in the interaction between randomness 
and computation and his work on that topic has appeared in journals 
including Nature, Science, and the Annals of Mathematics. For that work he 
has received an NSF CAREER award, a Sloan Fellowship, and an IDEAS 
Starting Grant from the European Research Council. In practice, he likes 
to think about scalability questions and holds 18 US Patents on topics 
ranging from load balancing and cache optimization to web search 
personalization. In his free time he enjoys overworking.

More information about the Ml-stat-talks mailing list