Algorithms, complexity and cryptography

The theory group does research in many different areas of theoretical computer science, such as combinatorics, computational complexity, algorithms, cryptography, coding theory, logic and graph theory. Many of our faculty are affiliated with other groups as well, such as the security group or the machine learning group. We also have strong connections with the mathematics department at UCSD.

The theory group and those interested in theory topics meet once in a week for the Theory Seminar, currently scheduled on Monday at 2-3pm.


  • Mihir Bellare  (cryptography, computer and network security, e-commerce and computational complexity theory)
  • Sanjoy Dasgupta (algorithmic statistics, unsupervised learning)
  • Russell Impagliazzo (proof complexity, cryptography, computational randomness, structural complexity, optimization heuristics)
  • Daniel Kane (boolean functions, derandomization, learning theory, polynomial
    threshold functions; Joint appointment in CSE and mathematics)
  • Shachar Lovett (computational complexity, algorithms, coding theory, pseudorandomness, additive combinatorics and algebraic methods in complexity)
  • Daniele Micciancio (lattices, coding theory, cryptography, symbolic security analysis)
  • Alon Orlitsky (Joint appointment with ECE)
  • Ramamohan Paturi (algorithms,  computational complexity, circuit complexity, learning theory, neural networks, parallel and optical computing)
  • Alexander Vardy (Joint appointment with ECE)
  • Victor Vianu (theory of query languages and logic)


  • Fan Chung Graham (spectral and extremal graph theory; Joint appointment in CSE and mathematics)
  • Ron Graham (scheduling theory, on-line algorithms, computational geometry, Ramsey theory, quasi-randomness)
  • T.C. Hu (combinatorial algorithms, mathematical programming, operatorations research, computer aided design)
  • Gill Williamson (combinatorics, algorithms)