Jakub Tarnawski

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.” The key contributions of Minzer’s dissertation are settling the complexity of testing monotonicity of Boolean functions and making a significant advance toward resolving the Unique Games Conjecture, one of the most central problems in approximation algorithms and complexity theory.

Property-testers are extremely efficient randomized algorithms that check whether an object satisfies a certain property, when the data is too large to examine. For example, one may want to check that the distance between any two computers in the internet network does not exceed a given bound. In the first part of his thesis, Minzer settled a famous open problem in the field by introducing an optimal tester that checks whether a given Boolean function (voting scheme) is monotonic.

The holy grail of complexity theory is to classify computational problems to those that are feasible and those that are infeasible. The PCP theorem (for probabilistically checkable proofs) establishes the framework that enables classifying approximation problems as infeasible, showing they are NP-hard. In 2002, Subhash Khot proposed the Unique Games Conjecture (UGC), asserting that a very strong version of the PCP theorem should still hold. The conjecture has inspired a flurry of research and has had far-reaching implications. If proven true, the conjecture would explain the complexity of a whole family of algorithmic problems. In contrast to other conjectures, UGC has been controversial, splitting the community into believers and skeptics. While progress toward validating the conjecture has stalled, evidence against it had been piling up, involving new algorithmic techniques.

In the second part of his dissertation, Minzer went halfway toward establishing the conjecture, and in the process nullified the strongest known evidence against UGC. Even if UGC is not resolved in the immediate future, Minzer’s dissertation makes significant advances toward solving research problems that have previously appeared out of reach.

Minzer is a postdoctoral researcher at the Institute for Advanced Study (IAS) in Princeton, New Jersey, and will be joining MIT as an Assistant Professor in the fall of 2020. His main research interests are in computational complexity theory, PCP, and analysis of Boolean functions. Minzer received a BA in Mathematics, as well as an MSc and PhD in Computer Science from Tel Aviv University.

Honorable Mentions for the 2019 ACM Doctoral Dissertation Award go to Jakub Tarnawski, École polytechnique fédérale de Lausanne (EPFL) and JiaJun Wu, Massachusetts Institute of Technology (MIT).

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.

JiaJun Wu’s dissertation, “Learning to See the Physical World,” has advanced AI for perceiving the physical world by integrating bottom-up recognition in neural networks with top-down simulation engines, graphical models, and probabilistic programs. Despite phenomenal progress in the past decade, current artificial intelligence methods tackle only specific problems, require large amounts of training data, and easily break when generalizing to new tasks or environments. Human intelligence reveals how far we need to go: from a single image, humans can explain what we see, reconstruct the scene in 3D, predict what’s going to happen, and plan our actions accordingly.

Wu addresses the problem of physical scene understanding—how to build efficient and versatile machines that learn to see, reason about, and interact with the physical world. The key insight is to exploit the causal structure of the world, using simulation engines for computer graphics, physics, and language, and to integrate them with deep learning. His dissertation spans perception, physics and reasoning, with the goal of seeing and reasoning about the physical world as humans do. The work bridges the various disciplines of artificial intelligence, addressing key problems in perception, dynamics modeling, and cognitive reasoning.

Wu is an Assistant Professor of Computer Science at Stanford University. His research interests include physical scene understanding, dynamics models, and multi-modal perception. He received his PhD and SM degree in Electrical Engineering and Computer Science from MIT, and Bachelor’s degrees in Computer Science and Economics from Tsinghua University in Beijing, China.