Abstract:
Optimization is fundamental in many areas of science, from computer
science and information theory to engineering and statistical
physics, as well as to biology or social sciences. It typically
involves a large number of variables and a cost function depending on
these variables. Optimization problems in the NP-complete class are
particularly difficult, it is believed that the number of operations
required to minimize the cost function is in the most difficult cases
exponential in the system size. Many famous combinatorial problems
belong to this class - for the sake of concreteness we will focus
mainly on the problem of graph coloring.
Seemingly unrelated to graph coloring is the fascinating physics of
the glass transition and glassy state of matter. Almost every liquid
when cooled down fast enough undergoes a glass transition, yet the
properties of the glassy state of matter are one of the most
mysterious and discussed subjects of classical physics. The abrupt
increase in viscosity of a glassy material when the temperature is
decreased by few percent is unseen in nature out of atomic or cosmic
scales. And the relaxation to equilibrium in a glassy material is one
of the slowest processes nature knows.
In this seminar I will explore the connection between glassy systems
and hard optimizations problems. I will show how algorithmical
hardness of certain optimization problems is related to their
glassiness. And how we can use methods developed to study glasses to
designs new powerful algorithms and to gain insights about which
problems are hardest ones. No prior knowledge of any of the subjects
is needed.
