\begin{figure}\psfig{figure=figure-never-delete.ps,width=2.5in}
\end{figure}

Theoretical Computer Science
at the University of Rochester

Our theory group consists of three faculty members. Lane Hemaspaandra, who has been an NSF Presidential Young Investigator, has won the Albert von Humboldt Foundation's Bessel Award, is a Distinguished Scientist of the ACM, serves on the editorial board of the journals Computational Complexity, Information Processing Letters, and Journal for Universal Computer Science, and is the complexity theory columnist for SIGACT News and the Computational Complexity area moderator for the ACM Computing Research Repository. He has published over one hundred journal papers and book chapters. He coauthored the book ``The Complexity Theory Companion'' with Mitsunori Ogihara, coauthored the book ``Theory of Semi-Feasible Algorithms'' with Leen Torenvliet, and co-edited the book ``Complexity Theory Retrospective II'' with Alan Selman. Joel Seiferas has done wide-ranging work spanning algorithms and complexity theory. He is the author of the Machine-Independent Complexity chapter of the Handbook of Theoretical Computer Science. He has published about twenty-five journal papers and book chapters. Daniel Stefankovic, who with a 2005 Ph.D. is the newest addition to our group, has broad interests centered upon algorithms and classification. He has published over fifteen journal papers.

The theory group pursues an active and intensive research effort in theoretical computer science, focusing on algorithms and computational complexity, and on their applications in a wide variety of fields. Due to the small and intensely research-oriented nature of our Ph.D. program, a student coming here will quickly be in the midst of that effort. For example, current areas of research activity here that a student might jump into include the study of: computational social choice theory and complexity-theoretic aspects of elections; complexity-theoretic aspects of security and fault-tolerance; development of algorithms for curves on surfaces; the power of counting-based computation; the power of probabilistic computation; the power of unambiguous computation; the importance of query order when accessing databases; string-matching algorithms; number-theoretic algorithms; cryptography; circuit theory; the study of efficient algorithms for complex sets; and the performance of heuristic algorithms.

Regarding our faculty members' particular research interests, and recent news, Professor Hemaspaandra's interests are broad, and during the past decade he has collaborated with over thirty researchers. He has long-term interests in computational complexity theory, computational social choice, computational politics, quantum computing, probabilistic computation, approximate computation, heuristic algorithms, algorithms from complexity, simulated annealing algorithms, fault-tolerance, data compression, cryptography, circuit theory, query order, inherent complexity of inverse problems, overhead-free computation on large objects, complexity of network structure recovery problems, security, and semi-feasible computation. Recent papers by Professor Hemaspaandra, joint with with URCS students and visitors, have shown that all context-free languages can be accepted in polynomial time with absolutely no space overhead, have proven that all superlinear inverse problems are coNP-hard, have yielded new broad-brush tools to classify problem complexity, have given strong evidence for the power of quantum computing, have explored the computational issues involved in evaluating, controlling, and manipulating election systems, have explored the power of small advice, and have established that for many tasks regarding polynomial-time functions algebraic properties can be added without any computational cost. Professor Hemaspaandra's Ph.D. students and postdocs have moved on to tenured and tenure-track positions at a broad range of schools in the US and overseas.

Professor Seiferas's interests span the areas of complexity, algorithms, and automata. He is particularly interested in sorting networks, including the Ajtai-Komlós-Szemerédi sorting network and the issue of generalizing Batcher's bitonic method. He is also working on making the PCP theorem's proof as clean and broadly accessible as possible. He current and recent supervision includes work on e-cash and peer-to-peer network algorithms, including routing, load balancing, and membership-management algorithms.

Professor Stefankovic's 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. Daniel, together with Marcus Schaefer, solved a 30 year old problem of Sinden, Graham, and Kratochvil, showing that ``string graphs'' (i.e., intersection graphs of Jordan curves in the plane) can be algorithmically recognized. In joint work with Marcus Schaefer and Eric Sedgwick he developed polynomial-time algorithms for classic algorithmic problems on simple curves in surfaces, which led to a complete resolution of the complexity of the string graph problem.

In addition to working with our students, the theory group has collaborated extensively with other researchers inside and outside of the University of Rochester. One of our close collaborations is with the theory group at the Rochester Institute of Technology: Professors Ivona Bezakova, Edith Hemaspaandra, Christopher Homan, and Staszek Radziszowski. In addition to multiple ties through student advising and joint research projects, the two groups sponsor the fortnightly Rochester Theory Seminar (affectionately known as the Theory Canal Seminar, due to our proximity to the historic Erie Canal). Our department has also participated in international collaboration grants with computational complexity research groups in Germany and Japan. Professor Hemaspaandra's work on computational politics involves researchers from six schools, and started during his Bridging Fellowship at the University of Rochester's Department of Political Science. Professor Stefankov works closely with Eric Vigoda of Georgia Tech and Marcus Schaefer of DePaul.

The web page http://www.cs.rochester.edu/research/ contains full details, background, and publications lists for many of our major theory projects, in particular:

And the web page
http://www.cs.rochester.edu/u/www/u/lane/theory-at-ur-contributions.html
contains our (somewhat propaganda-ish) overview of the group's key research contributions over time.

Our department benefits from its relatively small size in a number of ways, starting with the student, faculty, and staff collegiality and shared infrastructure that maintains a single-family atmosphere. Students are funded as long as they make adequate academic progress, and our stipend levels are very competitive. Students choose their own advisors on intellectual grounds, independent of money considerations. Our Ph.D. qualifying process is designed to ramp students smoothly from courses to independent research in at most two years. Our apprenticeship model of advising gets students quickly into research, travel, publication, and presentation. Our placement record is excellent. Our laboratories are first rate, and access to them is immediate.

General information on the department and electronic application material is available from the department's home page at http:/www.cs.rochester.edu/, and from here one can also visit the home pages of our faculty members and our entire department's research project descriptions. Fees are waived for early applications.



Maintained by: Lane A. Hemaspaandra