Theory
![](https://www.cs.columbia.edu/wp-content/uploads/2022/04/WebsiteImage_2021_SIGecom-Test-of-Time-Award.jpg)
Papadimitriou and Chen's influential papers settled the complexity of computing a Nash equilibrium.
![](https://www.cs.columbia.edu/wp-content/uploads/2023/07/Carousel_2023-Mihalis-Fest.jpg)
The three-day celebration honors the contributions of Mihalis Yannakakis to science on the occasion of his 70th birthday.
![](https://www.cs.columbia.edu/wp-content/uploads/2023/09/WebsiteImage_2023_MihalisYBdayFest.jpg)
The Theory Group recently hosted a three-day workshop in honor of Professor Mihalis Yannakakis' 70th birthday.
About
The group does research on the fundamental capabilities and limitations of efficient computation.
In addition, they use computation as a lens to gain deeper insights into problems from the natural, social, and engineering sciences.
The group is highly collaborative, both within Columbia and among peer institutions. They hold a weekly Theory Lunch and a bi-weekly Student Seminar. Most graduate students have (at least) two advisors and collaborate with several professors and other students. Some of the faculty are cross-listed with the IEOR department and the Data Science Institute.