Core Research Area 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 that 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 three 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.

The research program of Dr. John Case, Professor Emeritus, includes computational learning theory a.k.a. inductive inference as well as machine self-reference. He is interested in application of his theory work to cognitive science, understanding the reflective component of consciousness, philosophy of science, and applied machine learning. His research also includes the application of computability-theoretic techniques to the study of the structure, succinctness, and complexity of programs --- including and especially the complexity of programs that learn --- but also the complexity of learned programs.

Dr. Errol Lloyd, a Professor and Department Chair, 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. 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 and recent fields of application include bin packing and problems in ad hoc networks.

Dr. B. David Saunders works in exact linear algebra computation, both the theoretical and practical aspects. The theoretical aspects concern algorithms for matrix operations (see the theory section). The practical aspects involve implementation in the C++ library LinBox, which is under development by an international team. This includes implementations that take advantage of multicore and specialty hardware such as GPUs. Algebraic tools for computation over finite fields are extensively developed and used to solve integer and rational matrix problems. Large problems involving terabytes of data are handled.

Learn about Computational Labs

Current Faculty

Errol L. Lloyd, Professor: Design and analysis of algorithms, especially approximation algorithms for NP-hard problems.

B. David Saunders, Professor (joint appointment with Mathematical Sciences): Exact linear algebra; Dense, sparse, and structured integer matrix computations


CISC 601 Elements of Theory of Computation
CISC 604 Logic in Computer Science
CISC 621 Algorithm Design and Analysis
CISC 801 Advanced Computability Theory
CISC 805 Computational Learning Theory

Bookmark and Share