17 lipca 2020 20:57

Rozdano nagrody ACM za najlepsze prace doktorskie. Wyróżnienie za obronioną w 2019 roku na École Polytechnique Fédérale de Lausanne (EPFL) rozprawę doktorską otrzymał absolwent naszych studiów magisterskich Jakub Tarnawski -  obecnie pracownik Microsoft Research.

photo


Jakub Tarnawski’s dissertation “New Graph Algorithms via Polyhedral Techniques” made groundbreaking algorithmic progress on two of the most central problems in combinatorial optimization: the matching problem and the traveling salesman problem. Work on deterministic parallel algorithms for the matching problem is motivated by one of the unsolved mysteries in computer science: does randomness help in speeding up algorithms? Tarnawski’s dissertation makes significant progress on this question by almost completely derandomizing a three-decade-old randomized parallel matching algorithm by Ketan Mulmuley, Umesh Vaziriani, and Vijay Vazirani.

The second major result of Tarnawski’s dissertation relates to the traveling salesman problem: find the shortest tour of n given cities. Already in 1956, George Dantzig et al. used a linear program to solve a special instance of the problem. Since then the strength of their linear program has become one of the main open problems in combinatorial optimization. Tarnawski’s dissertation resolves this question asymptotically and gives the first constant-factor approximation algorithm for the asymmetric traveling salesman problem.

Tarnawski is a researcher at Microsoft Research. He is broadly interested in theoretical computer science and combinatorial optimization, particularly in graph algorithms and approximation algorithms. He received his PhD from EPFL and an MSc in Mathematics and Computer Science from the University of Wrocław, Poland. (https://awards.acm.org/about/2019-doctoral-dissertation)