Research in applied computation theory applies rigorous mathematical methods to the study of fundamental problems in computing.

A major theme in applied computation theory is the design and analysis of combinatorial algorithms for problems on graphs and other discrete structures, which model problems such as physical design of VLSI circuits. Algorithms are designed for traditional single processor computers, for highly parallel multiprocessor computers, and for distributed systems of computers connected by communication networks. Algorithms are analyzed to determine their efficiency. The efficiency of an algorithm is expressed in terms of the resources that it uses, such as running time, memory space, or number of processors. A careful analysis provides insight into the performance of an algorithm.

The analysis of an algorithm yields an upper bound on the computational complexity of a problem, telling us what is possible. A deep analysis of a problem may yield a lower bound on its complexity, telling us what is impossible.

Research in computational complexity theory is directed to understanding when efficient algorithms exist. Occasionally, nonconstructive techniques can be used to prove the existence of efficient algorithms without specifying them explicitly. Some problems are solvable in principle but cannot be solved in practice, because they have no efficient algorithms. For these computationally infeasible problems, heuristic algorithms are designed and analyzed.

The University of Illinois at Urbana-Champaign