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. Muthuramakrishnan Venkitasubramaniam holds a visiting research associate professor appointment.
- 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.
- Kaave Hosseini
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
Anson Kahng will join URCS and UR's Goergen Institute for Data Science in July 2022. He received his PhD from Carnegie Mellon University and is currently 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.
- Joel Seiferas, emeritus
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, Visiting Research Associate Professor
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 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.
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.
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.
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.