Skip to Content

Theory

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)
  • 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)

Recent Publications

Hardness of SIS and LWE with Small Parameters, Daniele Micciancio, and Chris Peikert, CRYPTO, Volume 8042, p.21-39, (2013). LNCS.
Full analysis of PRINTcipher with respect to invariant subspace attack: efficient key recovery and countermeasures, S. Bulygin, Michael Walter, and J. Buchmann, Designs, Codes and Cryptography, (2013).
Improved algebraic side-channel attack on AES, M. S. E. Mohamed, S. Bulygin, M. Zohner, A. Heuser, Michael Walter, and J. Buchmann, Journal of Cryptographic Engineering, Volume 3, Issue 3, p.139-156, (2013). PDF
New Bounds for Matching Vector Families, Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett, The 45th ACM Symposium on Theory of Computing (STOC 2013), (2013). [to appear] URL
Every locally characterized affine-invariant property is testable, Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett, The 45th ACM Symposium on Theory of Computing (STOC 2013), (2013). [to appear] URL
Many Weak Keys for PRINTcipher: Fast Key Recovery and Countermeasures, Stanislav Bulygin, Michael Walter, and Johannes Buchmann, CT-RSA, p.189-206, (2013). URL
Dirichlet PageRank and Ranking Algorithms Based on Trust and Distrust, Fan Chung Graham, Alexander Tsiatas, and Wensong Xu, Internet Mathematics, Volume 9, Number 1, p.113-134, (2013). URL
Algorithms for the Densest Sub-Lattice Problem, Daniel Dadush, and Daniele Micciancio, SODA, p.1103-1122, (2013). URL
Optimizing Guessing Strategies for Algebraic Cryptanalysis with Applications to EPCBC, Michael Walter, Stanislav Bulygin, and Johannes Buchmann, Inscrypt, (2012). PDF
Foundations of garbled circuits, Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway, ACM Conference on Computer and Communications Security, p.784-796, (2012). URL
RKA Security beyond the Linear Barrier: IBE, Encryption and Signatures, Mihir Bellare, Kenneth G. Paterson, and Susan Thomson, ASIACRYPT, p.331-348, (2012). URL


research_home | about seo