Theory
In this talk at the Simons Foundation, Alexandr Andoni describes how the tools and perspectives of high-dimensional geometry benefit search algorithms.
An average-case depth hierarchy theorem for Boolean circuits, a paper co-authored by Rocco A. Servedio and student Li-Yang Tan wins Best Paper at FOCS 2015.
The National Science Foundation (NSF) has awarded a $1.2M, four-year grant to Christos Papadimitriou and Mihalis Yannakakis for their proposal "Research in Algorithms and Complexity: Total Functions, Games, and the Brain."
About
Theory research includes computational complexity, algorithms and data structures, cryptography, quantum computing, computational geometry, approximation algorithms, computational game theory, algorithmic graph theory and combinatorics, online algorithms, computational learning theory, algebraic computation, optimization, randomness in computing, parallel and distributed computing, algorithmic coding theory, and theoretical aspects of areas such as networks, privacy, information retrieval, computational biology, and databases.
Theory of Computing Group 
Add to GMail