The solution space geometry of random constraint satisfaction problems
Amin Coja-Oghlan
Random instances of constraint satisfaction problems such as k-SAT or
k-Coloring are notoriously hard for many algorithmic techniques, in
particular if the density of the instance is close to the threshold
for the existence of a solution. Recent non-rigorous work from the
statistical physics community has led to new algorithms (e.g.,
"Survey Propagation") that perform emprically very well on random
instances. These algorithms are based on hypotheses about the
"solution space geometry" of random constraint satifaction problems,
i.e., the number and relative location of the solutions. In this talk
I will discuss these hypotheses as well as their algorithmic
implications, and present some recent mathematically rigorous work on
proving some of the hypotheses. Parts of the talk are based on joint
work with Dimitris Achlioptas and Alan Frieze.