Our research focuses on the theoretical foundations of computer science and related applications. Our methods frequently rely on rigorous mathematical proofs.
Topics:
- Algorithm Design:
- Graph algorithms, parallel and distributed algorithms, cache-efficient algorithms, algorithmic game theory, sublinear time algorithms.
- Computational Complexity:
- Circuit lower bounds, communication complexity, hardness of approximation.
- Randomness in Computation
- Randomized algorithms, pseudorandomness, expander graphs, error-correcting codes.
- Application Areas:
- Learning theory, Cryptography, Computational Biology.
- Quantum Information and Computation:
- Quantum algorithms and complexity theory; circuits, error correction, communication complexity; connections to condensed-matter physics and quantum gravity.
Courses:
- CS 388C Combinatorics & Graph Theory
- CS 388G Algorithms: Techniques & Theory
- CS 388H Cryptography
- CS 388M Communication Complexity
- CS 388P Parallel Algorithms
- CS 388R Randomized Algorithms
- CS 388T Theory of Computation
- CS 395T Coding Theory
- CS 395T Learning Theory
- CS 395T Pseudorandomness
- CS 395T Approximability
- CS 395T Algorithmic Game Theory
- CS 395T Quantum Complexity Theory
