Theory Research

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

The department's core faculty in theory consists of Lane A. Hemaspaandra, Joel Seiferas, Daniel Stefankovic, and Muthuramakrishnan Venkitasubramaniam.


Lane A. Hemaspaandra

Lane A. Hemaspaandra (BS Yale, MS Stanford, PhD 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 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

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

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

Muthuramakrishnan Venkitasubramaniam joined URCS in fall 2011. He received his PhD 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.

Project Pages

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: Reductions, Resources, and Robustness

This project focuses on complexity theory. Among its interests are: reductions; resources and models; robustness; and the power of heuristic algorithms.

Computational Social Choice Theory and Algorithmic Game 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.