Theory

Papers presented at STOC 2015

On the Complexity of Nash Equilibria in Anonymous Games / Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries / Indistinguishability Obfuscation for Turing Machines with Unbounded Memory / In Faster Canonical Forms for Primitive Coherent Configurations

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.

Paper by Columbia researchers named best paper at Computational Complexity Conference

"Settling the query complexity of non-adaptive junta testing" was named best paper at the 32nd Computational Complexity Conference (CCC), the top venue for research in computational complexity theory.

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.