Aviad Rubinstein is the recipient of the Association for Computing Machinery (ACM) 2017 Doctoral Dissertation Award for his dissertation “Hardness of Approximation Between P and NP.” In his thesis, Rubinstein established the intractability of the approximate Nash equilibrium problem and several other important problems between P and NP-completeness—an enduring problem in theoretical computer science.
For several decades, researchers in areas including economics and game theory have developed mathematical equilibria models to predict how people in a game or economic environment might act given certain conditions.
When applying computational approaches to equilibria models, important questions arise, including how long it would take a computer to calculate an equilibrium. In theoretical computer science, a problem that can be solved in theory (given finite resources, such as time) but for which, in practice, any solution takes too many resources (that is, too much time) to be useful is known as an intractable problem. In 2008, Daskalakis, Goldberg and Papadimitriou demonstrated the intractability of the Nash equilibrium, an often-examined scenario in game theory and economics where no player in the game would take a different action as long as every other player in the game remains the same. But a very large question remained in theoretical computer science as to whether an approximate Nash equilibrium (a variation of the Nash equilibrium that allows the possibility that a player may have a small incentive to do something different) is also intractable.
Rubinstein’s dissertation introduced brilliant new ideas and novel mathematical techniques to demonstrate that the approximate Nash equilibrium is also intractable. Beyond solving this important question, Rubinstein’s thesis also insightfully addressed other problems around P and NP completeness, the most important question in theoretical computer science. Rubinstein is a postdoctoral researcher at Harvard University and will be starting an appointment as an Assistant Professor at Stanford University in the fall of 2018. He received a PhD in Computer Science from the University of California, Berkeley, an MSc in Computer Science from Tel Aviv University (Israel) and a BSc in Mathematics and Computer Science from Technion (Israel).
Honorable Mentions for the 2017 ACM Doctoral Dissertation Award went to Mohsen Ghaffari, who received his PhD from the Massachusetts Institute of Technology’s Department of Electrical Engineering and Computer Science (MIT EECS) and Stefanie Mueller, who received her PhD from the Hasso Plattner Institute (Germany).
In Ghaffari’s dissertation, “Improved Distributed Algorithms for Fundamental Graph Problems,” he presents novel distributed algorithms that significantly lower the costs of solving fundamental graph problems in networks, including structuring problems, connectivity problems, and scheduling problems. Ghaffari’s dissertation includes both breakthrough algorithmic contributions and interesting methodology. The first part of the dissertation presents a new maximal independent set (MIS) algorithm, which is a breakthrough because it achieves a better time bound than previous algorithms for this three-decades-old problem. The second part of the dissertation contains a collection of related results about vertex connectivity decompositions. Finally, in the third part of his dissertation, Ghaffari introduces a time-efficient algorithm for concurrent scheduling of multiple distributed algorithms. Ghaffari is an Assistant Professor of Computer Science at ETH Zurich. He received a PhD and SM in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology and received a double major in Computer Science and Electrical Engineering from Sharif University (Iran).
Mueller’s dissertation, “Interacting with Personal Fabrication Devices,” demonstrates how to make personal fabrication machines interactive. Her approach involves two steps: speeding of batch processing and turn taking, and real-time interaction. Her software systems faBrickator, WirePrint and Platener allow users to fabricate 10 times faster, a process she calls low-fidelity fabrication or low-fab. In her dissertation she also outlines how to add interactivity. Constructable, a tool she developed, allows workers to fabricate by sketching directly on the workpiece, causing a laser cutter to implement these sketches when the user stops drawing. Another of Mueller’s tools, LaserOrigami, extends this work to 3D. Mueller is an Assistant Professor of Computer Science at MIT EECS and MIT CSAIL. She received a PhD in Computer Science as well as an MSc in IT-Systems Engineering from the Hasso Plattner Institute (Germany). Earlier, she received a BSc in Computer Science and Media from the University of Applied Science Harz (Germany).
