Data: poniedziałek, 20 maja 2024 r., godz. 10:00
Miejsce: Aula A
Prelegent: prof. David Gamarnik
Tytuł: Turing in the shadows of Nobel and Abel: an untold algorithmic story behind two recent prizes.
Abstrakt: 2021 Nobel Prize in physics was awarded to Giorgio Parisi for his contribution to understanding a mysterious matter called a spin glass. 2024 Abel Prize in mathematics was awarded to Michel Talagrand for laying down mathematically rigorous foundations of this work. What remained in the shadows though is a profound contribution that both them had on the field of algorithms and algorithmic complexity of random structures and combinatorics.
We will discuss how the ideas from the physics of spin glasses revolutionized our understanding of which optimization problems over random structures are algorithmically easy, which are not, and why. These ideas led to a remarkably precise characterization of this algorithmic (in)tractability via understanding their solution space geometry and phase transition. Below the phase transition fast algorithms exist, while above the transition point large classes of algorithms can be ruled out due to complex solution space geometry. In some sense, algorithmically easy problems are ''liquid'' and the algorithmically hard problems are ''rigid'' or ''solid''. In our talk we will make this characterization mathematically precise.
Prelegent: David Gamarnik is a Professor of Operations Research at the Massachusetts Institute of Technology. He received B.A. in mathematics from New York University in 1993 and Ph.D. in Operations Research from MIT in 1998. Since then he was a research staff member of IBM T.J. Watson Research Center, before joining MIT in 2005.
His research interests include discrete probability, optimization and algorithms, quantum computing, statistics, machine learning, and stochastic processes. He is a fellow of the American Mathematical Society, the Institute for Mathematical Statistics, and the Institute for Operations Research and Management Science. He is received Erlang Prize and the Best Publication Award from the Applied Probability Society of INFORMS. He is a member of the editorial board of Mathematics of Operations Research and was a member of editorial boards of Annals of Applied Probability, Operations Research, Stochastic Systems and Queueing Systems journals.