Columbia University in the City of New York

Theory

Christos Papadimitriou Named Recipient of 2022 IEEE Computer Society Women of ENIAC Computer Pioneer Award

For fundamental contributions to Computer Science, via the development of the theory of algorithms and complexity, and its application to the natural and social sciences.

Five Research Papers Accepted to FOCS 2025

Several of our faculty and students had their papers accepted, contributing new insights to areas such as algorithms, complexity theory, and cryptography.

Myths and Realities of Quantum Computing

At the BRITE ’25 conference, Henry Yuen broke down and shared his insights on the pace of advancement of quantum computing and what it will likely impact in the future, and what it won’t.

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.