Our research focuses on the theoretical foundations of computer science and related applications. Our methods frequently rely on rigorous mathematical proofs.
- Algorithm Design:
- Graph algorithms, parallel and distributed algorithms, cache-efficient algorithms, algorithmic game theory.
- 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.
- CS 353 Theory of Computation
- CS 357 Algorithms
- CS 388H Cryptography
- CS 388P Parallel Algorithms
- CS 388G Graduate Algorithms
- CS 388C Combinatorics and Graph Theory
- CS 395T Algorithmic Game Theory
- CS 395T Coding Theory
- CS 395T Learning Theory
- CS 395T Pseudorandomness
- CS 395T Approximability