2019 EPFL doctorate Award - Finalist – Damian Straszak
© 2019 EPFL - D. Straszak
Special distinction from the selection committee to Damian Straszak for his thesis “New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials”
EPFL thesis n°8957 (2018)
Thesis director: Prof. N. Vishnoi
Optimization is a fundamental tool in science. The recent advances in applying optimization to important problems in biology, economy, physics and statistics bring new challenges to algorithm design. The first challenge is related to the ever-growing size of instances, these optimization problems need to be solved for, which forces the underlying algorithms to run in time linear in their input size. The second challenge relates to the emergence of new, hard problems which need to be solved even though being considered computationally intractable because of NP-completeness or non-convexity.
The first part of this thesis attempts to tackle the former challenge: efficiency. We study new algorithms for classical combinatorial problems based on continuous dynamical systems inspired by the study of a slime mold Physarum polycephalum. We perform a rigorous mathematical analysis of these dynamical systems and extract from them new, fast algorithms.
In the second part, we develop new tools to approach the challenge of intractability. We study hard discrete optimization problems as well as their sampling and counting counterparts, including counting matchings in graphs, computing permanents of matrices or sampling from determinantal point processes. We present a general framework, based on polynomials, for dealing with these problems computationally.
