Theory

Columbia computer scientists present four papers at FOCS

Columbia theoretical computer scientists presented four papers at the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS) held October 18-20 2015 in Berkeley, CA.

Xi Chen is 2015 Winner of the EATCS Presburger Award

Xi Chen was named this year’s recipient of the Presburger Award.

Rocco Servedio awarded NSF grant to study limits of computing

With his former student Li-Yang Tan (PhD ’14), he will use random projections to prove lower bounds on Boolean circuits.

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.