The University of Rochester Computer Science Department has put together on-line “measures of excellence” information regarding the research contributions of the faculty members from the department's various research areas. The present page, in that context, regards the contributions of the URCS Theory Group; see also the theory people/projects page. We apologize for the somewhat group-self-promoting flavor of the present page, but that is a bit inherent in the requested task and in the nature of such pages. (P.S. We very much encourage any researchers or prospective students interested in learning more about the work described on this page, or obtaining the papers described, to contact us. We are enthusiastic about this work and love collaboration.)

The URCS theory group is internationally known for its work on complexity and algorithms. Among the many notions introduced in papers authored or coauthored by theory group faculty members are the Boolean Hierarchy, bribery in elections (studied, formally, algorithmically and complexity-theoretically) the complexity theory of hardest closure properties, destructive control of elections, enumerative approximation, frequently self-knowingly correct algorithms, locally positive reductions, membership comparability, modulo-based election hybridization, multimode electoral control, near-testability, nondeterministic selectivity-algorithm theory, the no-search easy-hard technique, optimal advice, optimal lowness, path-probabilistic complexity classes such as BPPpath, and universally serializable programs. These notions have become broadly influential within the field, and have been central in countless papers by researchers the world over.

Among the important complexity-theoretic results authored or coauthored by theory group faculty members are: the strong exponential hierarchy collapses; two heads on one tape are better than two single-head tapes, but no better than four; multiple counters are no better than one single-head tape; enumerative approximation is no easier than exact solution for #P functions; (proper) subtraction is a hard closure property for #P; probabilistic one-bit bottleneck machines suffice to accept all sets from the polynomial hierarchy; NP lacks unique solutions unless the polynomial hierarchy collapses; and nondeterministic time has very tight hierarchy theorems.

The theory group also does pathbreaking work in applications of theory to other areas. Papers coauthored by Prof. Lane A. Hemaspaandra have: shown that finding the winner in Lewis Carroll's 1876 election system is complete for parallel access to NP; proven dichotomy theorems that for broad classes of election systems identify the source of complexity for the manipulation and bribery problems; constructed an (artificial) election system that is computationally resistant to all twenty standard types of control; proved that Llull's (natural) thirteenth-century election system is computationally resistant to all ten standard types of constructive electoral control attacks; proved that in a black-box setting there are problems solvable in polynomial time on a quantum computer that on any classical computer requires exponential time almost everywhere; obtained apportionments of the US House of Representatives that are provably more power-fair than those obtained by the Huntington-Hill apportionment algorithm that is currently mandated by law; shown that if any one-way function exists then strong, total, commutative, associative one-way functions exist. Prof. Daniel Stefankovic's work can be explored via our theory project pages. Prof. Muthu Venkitasubramaniam has made broad contributions to 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, Muthu proposed a unified framework to efficiently realize any secure multiparty computation task with concurrent security; some examples of such tasks include anonymous electronic elections, privacy-preserving auctions, and fault-tolerant distributed computing. Emeritus Professor Joel Seiferas discovered the directed acyclic word graph data structure and its close relationship to suffix trees, and with Galil found ways to reduce and even eliminate extra space usage in linear-time string-matching algorithms. Seiferas did foundational work on retiming and simulating enhanced synchronous cellular automata. He also, with Fischer and Meyer, strengthened the nondeterministic time and space hierarchy theorems.

One thing we theory faculty members would like to stress is the high degree of collaboration between students, visitors, and faculty here, which has been utterly central in obtaining the results mentioned above. Graduate students here typically work in a mixture of modes during their time here. For a first paper, students often work closely with their advisor on some research idea of the advisor (or the student!). Soon, students are doing a rich range of work, including individual papers and papers joint with other students, faculty members, and visitors. Speaking of visitors, the theory group for over a decade has hosted a stream of excellent postdocs and other visitors, who form a very valuable resource for our students. These visitors have come from many countries (Germany, Holland, Russia, China, and Japan) and have been supported by a variety of agencies and highly competitive fellowships program, including the Fulbright program, the National Academy of Sciences/National Research Council Collaboration in Basic Science and Engineering Program, the NATO Postdoctoral Science Fellowship program, the (German) DAAD and DFG, the (Dutch) NWO, the (Japanese) JSPS, and the (Italian) Ministero della Pubblica Istruzione. Yet another resource for theory students is the theory group at the Rochester Institute of Technology. The UR and RIT theory groups have fortnightly joint seminars, and RIT's theory faculty members are active participants in reseach projects jointly with UR faculty and students, bringing to bear their particular advanced expertises---for example those of Prof. Staszek Radziszowski in graph algorithms and combinatorics, of Prof. Edith Hemaspaandra in the connections between complexity theory and logic, of Prof. Chris Homan in complexity, elections, and cryptography, and of Prof. Ivona Bezakova on discrete algorithms. Simply put, students coming here will find themselves in a close, concerned, supportive community working to discover new knowlege, and trying to help each other become better and better equipped to do so.