Algorithms, complexity and cryptography

Overview

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. We also have a Theory Reading Group currently scheduled on Friday 10am-12pm.

For a current list of theory-related seminars and courses, see the Theory Activities page.

CSE Department Faculty

  • Mihir Bellare  (cryptography, computer and network security, e-commerce and computational complexity theory)
  • 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)
  • 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)
  • Ramamohan Paturi (algorithms,  computational complexity, circuit complexity, learning theory, neural networks, parallel and optical computing)
  • Sanjoy Dasgupta (algorithmic statistics, unsupervised learning)
  • Victor Vianu (theory of query languages and logic)

Professor Emeritus

  • Gill Williamson (combinatorics, algorithms)
  • T.C. Hu (combinatorial algorithms, mathematical programming, operatorations research, computer aided design)

Faculty in Other Departments

Current graduate students

Current Postdocs and Visiting Researchers

  • Leo Ducas

Alumni (graduate students)

Postdocs and Visiting Researchers (past)