Center for Algorithms and Theory of Computation

The goal of research in theoretical computer science is to produce results, supported by rigorous proof, about problems dealing with computers and their applications. The questions to be investigated are often motivated by practical problems, but the goal of understanding the fundamental structure of the problem is often as important as producing a solution of immediate applicability. Despite this emphasis, it turns out that results that first might appear to be only of theoretical value are sometimes of profound relevance to practical problems.

In particular, one of the major subareas of theoretical computer science, and the one pursued by the faculty and graduate students at UCI, is concrete complexity: We look at specific problems and try to determine the complexity (i.e., the amount of resources required) for obtaining a solution. Our work falls into three main areas: design of algorithms and data structures; analysis; problem complexity.