Theory

Overview

Located along the pacific in one of the most beautiful locations of the US, San Diego, UC San Diego provides nothing less than a perfect environment for theoretical work. The rich contribution of the group to the theory community is a witness to this fact. The group has a history of producing research works which form the foundation for many areas in theoretical computer science, like cryptography, combinatorics, computational complexity and graph theory. We work hard to continue providing fundamental contributions in all areas of the field. We are on a constant lookout for energetic researchers in the area to add new dimensions to research in the group. We have a very good interaction with the mathematics department of UCSD.

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

CSE Department Faculty

• Mihir Bellare
  • Areas of interest include cryptography, computer and network security, e-commerce and computational complexity theory.
• Fan Chung Graham (Joint appointment in CSE and Mathematics)
  • Her main research interests lie in spectral graph theory and extremal graph theory.  She has about 200 papers, in areas ranging from pure mathematics (e.g., differential geometry, number theory) to the applied (e.g., optimization, computational geometry, telecommunication and internet computing).
• Ron Graham
  • Several mathematical areas were started by Ron's work, such as worst case analysis in scheduling theory, on-line algorithms and amortized analysis in the Graham's scan in Computational Geometry, and his favorite topics on Ramsey Theory, and the recent work on quasi-randomness.
• Russell Impagliazzo
  • Areas of interest include proof complexity, the theory of cryptography, computational randomness, structural complexity, and trying to analyze optimization heuristics and other approaches to solving hard problems.
• Daniele Micciancio
  • His research interests include complexity of lattice and coding problems and their applications to cryptography, Symbolic analysis of cryptographic protocols and other topics in cryptography (e.g., zero knowledge proofs, cryptographic primitives with special properties)
• Ramamohan Paturi
  
  • His areas of interest include algorithms and complexity, circuit complexity, learning theory, neural networks, parallel and optical computing.
• Sanjoy Dasgupta
  • He is interested in algorithmic statistics and unsupervised learning.
• Victor Vianu
  • Areas of interest include theory of query languages and logic.

Professor Emeritus

• Gill Williamson
  • He is a prolific author of texts in the field of combinatorics and the design and analysis of algorithms.
• T.C. Hu
  • His reasearch interests include combinatorial algorithms, mathematical programming and operators research and computer aided design.

Faculty in Other Departments

• Sam Buss (Mathematics)
• Alon Orlitsky (ECE)
• Alexander Vardy (ECE)

Graduate Students (past)

• Chris Calabro
• Sashka Davis
• Ragesh Jaiswal
• Kirill Levchenko
• William Matthews
• Shengjun Pan
• Nan Zang
• Yi-Kai Liu
• Vadim Lyubashevsky
• Konstantin Pervyshev

Visiting Researchers (past)

• Josh Buresh Oppenheim
• Valentine Kabanets
• Martin Grohe
• Oliver Braun