Dor Minzer of Tel Aviv University is the recipient of the 2019 ACM Doctoral Dissertation Award for his dissertation, “On Monotonicity Testing and the 2-to-2-Games Conjecture.” Honorable Mentions go to Jakub Tarnawski of École polytechnique fédérale de Lausanne (EPFL) and JiaJun Wu of Massachusetts Institute of Technology.
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.