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, 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.


  • 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

Research Groups: