My research focuses on a core question in theoretical computer science: What can be computed efficiently? The study of algorithms and computational complexity is a mathematical discipline that lies at the foundation of Computer Science. It introduces a “Computational Lens” that helps explain phenomenon in areas that are seemingly unrelated to computing, including phenomenon in economics, in biology, and in physics. Central to all these fields are processes and systems that implicitly do complex computations. Hence, understanding the limits of computation helps explain why certain complex systems behave the way they do. An important example is my work on the complexity of Nash equilibrium. Nash’s theorem proves that every finite game admits an equilibrium, but my research suggests that there may be no efficient algorithm for finding the equilibrium, or even approximating it. Hence, the equilibrium, although it exists, may be inaccessible to computationally bounded players.
Awards and Achievements
- ACM Doctoral Dissertation Award