Theoretical Computer Science

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.

Courses:

  • CS 313 Logic, Sets, and Functions
  • CS 336 Analysis of Programs
  • CS 341 Automata Theory
  • 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 394C Algorithms for Computational Biology
  • CS 395T Algorithmic Game Theory
  • CS 395T Coding Theory
  • CS 395T Learning Theory
  • CS 395T Polynomials
  • CS 395T Pseudorandomness

Research Groups: