Theory Research

Theoretical computer science research at URCS focuses on algorithms, computational complexity, and randomness/pseudorandomness, and on their connections to and applications in a wide range of fields: combinatorics, computational social choice theory, cryptography, economics, Markov chains/counting, security, and much more.

The department's core faculty in theory consists of Lane A. Hemaspaandra, Kaave Hosseini, Anson Kahng, Joel Seiferas (emeritus), and Daniel Stefankovic. Professors of instruction Andrew Read-McFarland and Eustrat Zhupa are also expert theoretical computer scientists. Muthuramakrishnan Venkitasubramaniam holds a visiting research associate professor appointment.

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.


Lane A. Hemaspaandra
Professor of Computer Science

lane "at" cs.rochester.edu | (585) 275-1203
2317 Wegmans Hall

Interests: Computational social choice (elections, preference aggregation, power indices, etc.); Computational complexity theory (counting-based computation, probabilistic computation, unambiguous computation, the importance of query order when accessing databases, the study of efficient algorithms for complex sets, complexity-theoretic aspects of security, fault-tolerance, and data compression, etc.)

Lane A. Hemaspaandra (BS Yale, MS Stanford, PhD Cornell) is the recipient of an NSF Presidential Young Investigator Award, the Alexander von Humboldt Foundation's Bessel Research Award, and the SIGACT Distinguished Service Award. Lane's research interests include computational social choice theory, 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.


Kaave Hosseini
Assistant Professor of Computer Science

shossei2@ur.rochester.edu | (585) 275-7968
2507 Wegmans Hall

Interests: Theoretical computer science; Additive combinatorics; Pseudorandomness; Discrete Fourier analysis

Kaave Hosseini joined URCS in Fall 2021. Previously, he was a postdoctoral associate in the department of Mathematical Sciences at Carnegie Mellon University. He received his PhD at the University of California, San Diego. His research is in theoretical computer science and discrete mathematics. Conceptually speaking, some of his work has to do with the structure vs. randomness dichotomy and applications of this phenomenon in various areas such as computational complexity, algorithms, communication complexity, and additive combinatorics. Moreover, he has worked on explicit constructions of pseudorandom objects such as pseudorandom generators and extractors, which are objects with a wide range of applications in complexity theory and cryptography. 


Anson Kahng
Assistant Professor of Computer Science and Data Science

akahng2@cs.rochester.edu | (585) 275-1328
2401 Wegmans Hall

Interests: Computational social choice; Democracy and computer science; Economics and computation; Artificial intelligence; Theoretical computer science; Algorithmic game theory

Anson Kahng joined URCS and UR's Goergen Institute for Data Science in July 2022. He received his PhD from Carnegie Mellon University and was a Postdoctoral Fellow at the University of Toronto. Broadly, Anson's research interests lie at the intersection of theoretical computer science, artificial intelligence, and economics. More specifically, he is interested in the relationship between computer science and democracy, and he uses tools from computational social choice to analyze new democratic paradigms such as liquid democracy, participatory budgeting, and virtual democracy from the perspective of various desiderata including strategyproofness, robustness, and fairness, among others.


Andrew Read-McFarland
Assistant Professor of Computer Science (Instruction)


Joel Seiferas
Professor Emeritus of Computer Science

joel@cs.rochester.edu
3303 Wegmans Hall

Interests: Theoretical computer science; Computational complexity; Algorithms; Automata

Joel Seiferas (SB mathematics, SM and PhD computer science, MIT) 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
Professor of Computer Science

daniel.stefankovic@rochester.edu | (585) 275-5492
2315 Wegmans Hall

Interests: Theoretical computer science: graph theory, combinatorics, Fourier transform, Markov chains/counting, learning theory, phylogeny, game theory, graph equations, routing

Daniel Stefankovic joined URCS in July, 2005, after receiving his PhD 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
Visiting Research Associate Professor of Computer Science

muthuv@cs.rochester.edu

Interests: Cryptography; Complexity Theory

Muthuramakrishnan Venkitasubramaniam joined URCS in fall 2011. He received his PhD at Cornell University and did his postdoctoral studies at the Courant Institute of Mathematical Science, NYU, under the Computing Innovation Fellows (CIFellows) program. 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.


Eustrat Zhupa
Assistant Professor of Computer Science (Instruction)