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.