The goal of research in the Theory of Computation is to abstract the salient features of computational tasks, in order to permit their analysis in a setting unencumbered by the details of any particular technology. Ideas of direct and immediate practical applicability may emerge as byproducts of such work, but far more important in the long term is the conceptual framework provided. The close cooperation and interaction among all our faculty enable the theoretical work to be influenced by the present-day realities of computing, and help to ensure the relevance of that work to the future practice of computing.
One example of such a project concerns the development of a computational complexity theory for parallel computing systems. This work is aimed at finding general principles underlying such systems, with the eventual goal of applying these principles to the design and implementation of parallel systems, and to the solution of real problems on them. Current work includes definitions of and comparisons among various abstract models of parallel systems, study of interconnection networks and packet routing algorithms for parallel machines, design and analysis of efficient parallel algorithms, identification of ``inherently sequential'' problems (i.e., ones for which parallel systems offer little or no benefit), and implementation, measurement, and analysis of a variety of parallel data structures and algorithms on real parallel machines.
Other research projects include studies of distributed protocols, algorithms for computational geometry (e.g., for computer graphics or computer-aided design), probabilistic algorithms, structural aspects of complexity, and lower bounds on the computational complexity of natural problems.
Principal Investigators: Anderson, Beame, Ladner, Ruzzo, Tompa, Young