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 2pm.

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

Alumni (graduate students)

Postdocs and Visiting Researchers (past)

Recent Publications

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
On the Exact Complexity of Evaluating Quantified k-CNF, Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi, Algorithmica, Volume 65, Number 4, p.817-827, (2013). URL
Algorithms for the Densest Sub-Lattice Problem, Daniel Dadush, and Daniele Micciancio, SODA, p.1103-1122, (2013). URL
An equational approach to secure multi-party computation, Daniele Micciancio, and Stefano Tessaro, ITCS, p.355-372, (2013). URL
Semantic Security for the Wiretap Channel, Mihir Bellare, Stefano Tessaro, and Alexander Vardy, CRYPTO, p.294-311, (2012). URL
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
Adaptively Secure Garbling with Applications to One-Time Programs and Secure Outsourcing, Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway, ASIACRYPT, p.134-153, (2012). URL
On-line Ciphers and the Hash-CBC Constructions, Mihir Bellare, Alexandra Boldyreva, Lars R. Knudsen, and Chanathip Namprempre, J. Cryptology, Volume 25, Number 4, p.640-679, (2012). URL
Multi-commodity Allocation for Dynamic Demands Using PageRank Vectors, Fan R. K. Chung, Paul Horn, and Jacob Hughes, WAW, p.138-152, (2012). URL
Ranking and Sparsifying a Connection Graph, Fan Chung Graham, and Wenbo Zhao, WAW, p.66-77, (2012). URL
Braess's paradox in expanders, Fan Chung Graham, Stephen J. Young, and Wenbo Zhao, Random Struct. Algorithms, Volume 41, Number 4, p.451-468, (2012). URL

[Publications Archive]



by Dr. Radut.