Graduate Program in Theory of Computation

Theory of Computation is the core area of computer science that attempts to achieve deep understanding of computational processes by means of mathematical models, tools, and techniques. This understanding is important for its applications which include algorithm, compiler and VLSI design, the creation of intelligent technology, cognitive psychology, and philosophy.

Work in this broad area generally appeals to those who seek this understanding for any of the reasons it is important and who are attracted by the aesthetic, combinatorial, conceptual, and logical components of the thinking required.

At the University of Delaware there are two regular faculty members and occasional visiting faculty members in theory of computation and a resultant broad range of exciting research projects available for essential participation by computer science doctoral students specializing in theory.

Dr. Errol Lloyd, a Professor, is interested in the design and analysis of algorithms, particularly combinatorial algorithms for optimization problems.

A great many practical optimization problems are apparently too complex to solve exactly in any reasonable amount of time (many of these problems are NP-complete). When faced with such a problem, what is to be done? There are several possibilities. One is to develop algorithms that produce approximate solutions to the problem in question. For instance, when scheduling a set of jobs for execution on several processors, we might desire that the entire set of jobs be completed as soon as possible. Unfortunately, most versions of this problem are NP-complete, so finding truly minimum solutions is probably not possible. There is however an easy algorithm that will provide a schedule that is provably no longer than twice the optimal length. Another approach to hard optimization problems is to examine the situation more closely to determine if there are specific classes of instances of the problem that can be solved efficiently. A third approach is to prove that (subject to some technical considerations) no algorithm can reliably produce good approximations to a solution in a reasonable amount of time.

Dealing with hard optimization problems and considering such approaches is the focus of Professor Lloyd's work. The work includes formal results dealing with such things as the running times of algorithms, algorithm correctness, and on the goodness of the approximations produced by various algorithms. Experimental results on the goodness of the approximations are also of interest. Current or previous fields of application include: task scheduling, bin packing, VLSI design (routing and PLA folding), register allocation, and packet radio network scheduling and routing.

For more detailed information on Professor Lloyd's projects, click on his name above.

The research program of Dr. John Case, also a Professor, includes computational learning theory and lattice-connected computer models of parallel processing.

The first part of his current research program involves the mathematical theory of learning strategies for process-control (and games). In the model he is investigating, the learning mechanism has available at any time only a portion of the behavior of the process to control, equivalently, only a portion of the corresponding game tree. His investigation is principally theoretical and secondarily empirical but with each of these thrusts informing the other.

It is seen both theoretically and empirically that, many times, the knowing or learning of one task will enhance the feasibility or learnability of another. In the context of learning process-control he is investigating how to determine when knowing or learning one task will or will not enhance the learning of another.

In complex process-control situations the data-base about the process can become too large to handle. He is investingating the effects on computational learnability of bounding the amount of data remembered and also of bounding the number of queries allowed to the data-base. Furthermore he is studying the effects of this when using noisy data.

His primary research methods originally derived from mathematical logic and include recursion theory and self-reference arguments. He also contributes to extensions of these tools within both computational learning theory and computational complexity theory.

In the second part of his current reasearch program Dr. Case is developing the theoretical underpinning and basic algorithms for lattice-connected computers which are intended to provide useful, natural, massively parallel, analog simulations of physical motion. He expects applications to artificial intelligence and scientific computing. This project uses methods primarily from modern algebra and secondarily from combinatorics and number theory. In the future he hopes to develop a useful, associated programming environment which is transportable from one network of workstations to another.

For more detailed information on Professor Case's projects, click on his name above.

Courses

CISC 601 --- Elements of Theory of Computation,
CISC 604 --- Logic in Computer Science, and
CISC 621 --- Algorithm Design and Analysis.

Design and Analysis of Parallel Algorithms,
Computational Learning Theory, and
Recursive Function Theory.