The department's core faculty in Theory consists of Lane A. Hemaspaandra, Joel Seiferas, Daniel Stefankovic, and Muthuramakrishnan Venkitasubramaniam.
- Lane A. Hemaspaandra (B.S. Yale, M.S. Stanford, Ph.D. Cornell) is the recipient of an NSF Presidential Young Investigator Award and the Alexander von Humboldt Foundation's Bessel Research Award, and is an ACM Distinguished Scientist. Lane's research interests include computational social choice theory (see our CACM survey article), complexity, and algorithms. He and his collaborators have collapsed the strong exponential-time hierarchy, found the exact complexity of Lewis Carroll's 1876 election system, and constructed election systems that computationally resist all standard attacks. Lane has coauthored the books The Complexity Theory Companion and Theory of Semi-Feasible Algorithms and over one hundred book chapters and refereed journal papers, and holds many editorial positions.
- Joel Seiferas (S.B. mathematics, S.M. and Ph.D. computer science, M. I. T.) is author of the Machine-Independent Complexity chapter of the Handbook of Theoretical Computer Science and the chapter on the AKS sorting network in the Encyclopedia of Parallel Computing. Joel, too, has been named an ACM Distinguished Scientist, in recognition of fundamental research in automata-based complexity, simulations, algorithms, and lower bounds—research that includes major work on nondeterminism, hierarchies, and complexity classes; simulation of multihead tapes; lower bounds via Kolmogorov complexity; string matching; sorting networks; and cellular automata.
- Daniel Stefankovic joined URCS in July, 2005, after receiving his Ph.D. at University of Chicago. His research interests are in theoretical computer science, in particular: algorithmic problems on curves on surfaces, Markov chain sampling, algorithmic game theory, graph drawing, and applications of discrete and continuous Fourier transforms.
- Muthuramakrishnan Venkitasubramaniam joined URCS in Fall 2011. He received his Ph.D. at Cornell University and is a CI Fellow currently pursuing postdoctoral studies at Courant Institute of Mathematical Science, NYU. His research is in cryptography and its interplay with complexity theory, in particular: understanding secure composition of cryptographic protocols, minimal assumptions required for efficient constructions, intrinsic complexity of cryptographic primitives, and basing cryptography on NP-hardness. As part of his thesis, he proposed a unified framework to efficiently realize any secure multiparty computation task with concurrent security (STOC'09); some examples of such tasks include anonymous electronic elections, privacy-preserving auctions, and fault-tolerant distributed computing.
The URCS theory group works closely with the RIT (Rochester Institute of Technology) theory group, and the groups jointly run the Theory Canal seminar series.