Congratulations to my former student Dr. Dor Minzer for winning the ACM Doctoral Dissertation Award!
The Association for Computing Machinery (ACM) today announced that Dor Minzer receives 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 had 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.