Theory

Christos Papadimitriou Awarded the Harvey Prize

Mihalis Yannakakis Named Recipient of the 2020 EATCS Award

The EATCS Award committee selects Professor Mihalis Yannakakis as the recipient of the 2020 EATCS Award for his fundamental and deep contributions to a range of areas in theoretical computer science, including algorithms, complexity theory, combinatorial optimization, databases, and verification.

Alexandr Andoni on The Geometry of Similarity Search

In this talk at the Simons Foundation, Alexandr Andoni describes how the tools and perspectives of high-dimensional geometry benefit search algorithms.

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.