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 ReadMcFarland and Eustrat Zhupa are also expert theoretical computer scientists. Muthuramakrishnan Venkitasubramaniam holds a visiting research associate professor appointment.
Lane A. Hemaspaandra
Professor of Computer Science
lane "at" cs.rochester.edu  (585) 2751203
2317 Wegmans Hall
Interests: Computational social choice (elections, preference aggregation, power indices, etc.); Computational complexity theory (countingbased computation, probabilistic computation, unambiguous computation, the importance of query order when accessing databases, the study of efficient algorithms for complex sets, complexitytheoretic aspects of security, faulttolerance, 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 exponentialtime 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 SemiFeasible 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) 2757968
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) 2751328
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 ReadMcFarland
Assistant Professor of Computer Science (Instruction)
 areadmcf@cs.rochester.edu
 2105 Wegmans Hall
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 MachineIndependent 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 automatabased 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) 2755492
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
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 NPhardness. 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, privacypreserving auctions, and faulttolerant distributed computing.
Eustrat Zhupa
Assistant Professor of Computer Science (Instruction)
 ezhupa@cs.rochester.edu  (585) 2759499
 2107 Wegmans Hall
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.
Project Name  Brief Summary 

Applications of Discrete Mathematics in Computer Science  This project studies applications of discrete mathematics in computer science. The topics include combinatorics, counting, coding theory, game theory, learning theory and routing. 
Computational Complexity  This project focuses on complexity theory. Among its interests are: reductions; resources and models; robustness; structure in complexity theory, and the power of heuristic algorithms.

Computational Social Choice Theory  This project studies complexitytheoretic and algorithmic aspects of political science and economics—in particular, of voting theory and game theory. Our work ranges from experimental study of Congressional apportionment to theoretical studies of voting systems and cooperative game theory. We are particularly interested in the ways in which complexity can serve as a tool to protect elections from attacks. 
Graph drawing, computing with curves on surfaces, string graphs  This project studies theoretical problems arising in the area of graph drawing (network diagram visualization). Examples of topics studied are: variants of crossing numbers and their connections, generalizations of the concept of planarity, and algorithmic problems for curves on surfaces. 
Counting Classes  This project studies counting classes. The term "counting classes'' has come to refer to a certain collection of classes—such as #P, SPP, probabilistic classes, paritybased classes, etc.—that are defined in terms of the number of accepting paths of nondeterministic machines. 
SemiFeasible Algorithms  This project studies the properties of the semifeasible sets. A set is semifeasible (a.k.a. Pselective) exactly if there is a polynomialtime algorithm that given any two elements of the set chooses one, and does so in such a way that if of the two elements exactly one belongs to the set, the algorithm always chooses that one. This can model guided search. 
ComplexityTheoretic OneWay Functions, Cryptography, and Pseudorandom Generators  This project studies complexitytheoretic oneway functions, cryptography, and pseudorandom generators. One central focus is seeking characterizations regarding the existance of various types of oneway functions. Also of interest is the extent to which queries can be made without leaking information, and learning more about the connection between foundational complexitytheoretic notions and whether all pseudorandom generators are insecure. This project is in the worstcase idiom, i.e., it studies socalled complexitytheoretic oneway functions. 
Downward Collapses and Query Order  Everyone knows that it makes more sense to first look up in your online date book the date of the yearly Computational Complexity conference and then phone your travel agent to get tickets, as opposed to first phoning your travel agent (without knowing the date) and then consulting your online date book to find the date. In real life, order matters. This project seeks to determine whether one's everydaylife intuition that order matters carries over to complexity theory. It also seeks to find cases where collapsing powerful classes induces collapses in their weaker cousins. 
Sets of Low Information Content  This project focuses on classes of sets of low information content, such as sparse sets. 