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.
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
- Sam Buss (Mathematics)
- Alon Orlitsky (ECE)
- Alexander Vardy (ECE)
Current graduate students
Current Postdocs and Visiting Researchers
- Leo Ducas
Alumni (graduate students)
- Petros Mol (PhD 2013)
- Alexander Tsiatas (PhD 2012)
- Rafael Dowsley (MS 2012)
- Shengjun Pan (PhD 2012)
- Wenbo Zhao (PhD 2012)
- Panagiotis Voulgaris (PhD 2011)
- William Matthews (PhD 2011)
- Scott Yilek (PhD 2010)
- Tom Ristenpart (PhD 2009)
- Chris Calabro (PhD 2009)
- Todor Ristov (MS 2009)
- Vadim Lyubashevsky (PhD 2008)
- Sarah Shoup (MS 2008)
- Sashka Davis (PhD 2008)
- Ragesh Jaiswal (PhD 2008)
- Kirill Levchenko (PhD 2008)
- Nan Zang (PhD 2008)
- Saurabh Panjwani (PhD 2007)
- Yi-Kai Liu (PhD 2007)
- Alejandro Hevia (PhD 2007)
- Tadayoshi Kohno (PhD 2006)
- Anton Mityagin (PhD 2006)
- Jia Mao (PhD 2006)
- Alan Nash (PhD 2006)
- Adriana Palacio (PhD 2006)
- Bogdan Warinschi (PhD 2004)
- Alexandra Boldyreva (PhD 2004)
- Sara Miner More (PhD 2003)
- Nathan Segerlind (PhD 2003)
- Chanathip Namprempre (PhD 2002)
- Ted Carson (PhD 2001)
- Michel Abdalla (PhD 2001)
- Jeehea Lee (Ph.D 2001)
- Anand Desai (Ph.D 2000)
- Giovanni DiCrescenzo (PhD 1999)
- Francis Zane (PhD 1998)
- Markus Jakobsson (PhD 1997)
- Tassos Dimitriou (PhD 1996)
Postdocs and Visiting Researchers (past)
- Stefano Tessaro
- Nadia Heninger
- Daniel Lokshtanov
- Josh Buresh Oppenheim
- Valentine Kabanets
- Martin Grohe
- Oliver Braun