Algorithms and Complexity
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 STAR seminar (and for pizza of course), in which we present our own work or discuss recent interesting results in the area. We also have a number of visitor talks throughout the year which in conjunction with STAR, helps a lot in keeping up-to-date with the current research.
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.
- T.C. Hu
- His reasearch interests include combinatorial algorithms, mathematical programming and operators research and computer aided design.
- 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.
Faculty in Other Departments
- Sam Buss (Mathematics)
- Alon Orlitsky (ECE)
- Alexander Vardy (ECE)
Graduate Students
- Chris Calabro
- Sashka Davis
- Ragesh Jaiswal
- Kirill Levchenko
- William Matthews
- Shengjun Pan
- Nan Zang
- Yi-Kai Liu
- Vadim Lyubashevsky
- Konstantin Pervyshev
- Andrew Drucker
Visiting Researchers (past and present)
Conferences
Here is a list of important conferences in Theoretical Computer Science. These are organized by submission deadline.
| Conference | Submission Deadline | Location | Conference Dates |
|---|---|---|---|
| STOC 2007 | November 20, 2006 (7:59 pm EST) | San Diego, CA | June 11-13, 2007 |
| EUROCRYPT 2007 | November 7, 2006 | Barcelona, Spain | May 20 - 24, 2007 |
- Erik Demaine's List of Events: Provides a comprehensive list of events related to Theoretical Computer Science.
- ECCC: Electronic Colloquium on Coputational Complexity
- Cryptography Conference List by Mihir Bellare
Courses on Theoretical Topics
Various interesting courses on theoretical topics are offered throughout the year by faculty and visitors in the CSE and Math departments. Here is a list of these courses.
| Quarter | Course # | Course Title | Instructor |
|---|---|---|---|
| Fall 2007 | CSE 200 | Computability and Complexity | Daniele Micciancio |
| Fall 2007 | CSE 202 | Algorithms and Analysis | Mohan Paturi |
| Fall 2007 | CSE 207 | Modern Crytography | Mihir Bellare |
| Fall 2007 | CSE 209A | Topics in Algorithms, Complexity and Logic (STAR Seminar) | Daniele Micciancio |
