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).
