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.


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)



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.

 

Projects
Project NameBrief 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 complexity-theoretic 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, parity-based classes, etc.—that are defined in terms of the number of accepting paths of nondeterministic machines.

Semi-Feasible Algorithms

This project studies the properties of the semi-feasible sets. A set is semi-feasible (a.k.a. P-selective) exactly if there is a polynomial-time 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.

Complexity-Theoretic One-Way Functions, Cryptography, and Pseudorandom Generators

This project studies complexity-theoretic one-way functions, cryptography, and pseudorandom generators. One central focus is seeking characterizations regarding the existance of various types of one-way functions. Also of interest is the extent to which queries can be made without leaking information, and learning more about the connection between foundational complexity-theoretic notions and whether all pseudorandom generators are insecure. This project is in the worst-case idiom, i.e., it studies so-called complexity-theoretic one-way 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 everyday-life 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.