## Overview

Members of the Theory of Computation (Theoretical Computer Science) group aim to

- Understand the mathematical laws governing efficient computation, and
- Apply this understanding to address problems arising in other parts of computer science and mathematics, and in other fields such as neuroscience and physics.

## Our Research Areas

- Design and Analysis of Algorithms: Barak, Mitzenmacher, Nelson, Rabin, Singer, Valiant
- Computational Complexity: Barak, Nelson, Sudan, Vadhan, Valiant
- Logic in Computer Science: Lewis
- Error-Correcting Codes: Elkies, Mitzenmacher, Sudan, Vadhan
- Cryptography: Barak, Rabin, Vadhan
- Learning Theory & Cognitive Computation: Valiant
- Randomness in Computation: Barak, Mitzenmacher, Nelson, Rabin, Sudan, Vadhan
- Quantum Computation: Valiant
- Computational Algebra & Number Theory: Elkies, Rabin, Sudan
- Parallel Computation: Rabin, Valiant
- Streaming Algorithms: Mitzenmacher, Nelson
- Computational Mechanism Design & Game Theory: Chen, Singer, Parkes
- Data Privacy: Chen, Vadhan
- Graphics and Discrete Geometry: Gortler
- Approximability of Optimization Problems: Barak, Singer, Sudan