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

Research Groups: