Speaker
Lenka Zdeborova
(U Paris-Sud)
Description
We introduce the random `locked' constraint satisfaction
problems. When increasing the density of constraints, they
display a broad `clustered' phase in which the space of
solutions is divided into many isolated points. While the
phase diagram can be found easily, these problems, in their
clustered phase, are extremely challenging from the
algorithmic point of view: the best known algorithms all
fail to find solutions. We thus propose new benchmarks of
really hard optimization problems and provide insight into
the origin of their typical hardness.
