# Theory of Computation

#### Core Research Area in Theory of Computation

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.

#### 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

#### Courses

- 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

##### Laboratories - Theory of Computation

### Computational Learning Laboratory

**342 Smith Hall, Professor John Case.**

The members of the Computational Learning Laboratory do theoretical, mathematical work regarding abstract machine models of, among other things, learning and self-modeling.

### LinBox Laboratory

**119 Elkton Road, Professor David Saunders, Research Associate Professor David Wood.**

We design algorithms and high performance implementations for exact linear algebra computation. Exact linear algebra with matrices of integers is harder than the more widely used approximate linear algebra in floating point. Our work contributes to LinBox, a software library for solving exact systems exactly. It is developed by a team of researchers in the US, France, and Canada.

### Network Management and Optimization Laboratory

**342 Smith Hall, Professors Adarsh Sethi and Errol Lloyd.**

Network management involves the design of techniques for the monitoring and control of computer networks to ensure optimal performance and resource utilization. We focus on fault management whose aim is to detect, diagnose, localize, and recover from hardware and software failures and performance bottlenecks that may plague a network. We are also interested in the management of wireless networks including methods for managing mobility to provide seamless operation of network services.

In network optimization we aim to provide provably optimal or near optimal solutions to a range of power specification and control problems arising in wireless ad hoc and sensor networks. The primary focus is on topology control (assigning power levels to network nodes so as to achieve a specified network topology) in both stationary and mobile networks. Additional work includes the study of relay node placement and of power back off as a collision resolution mechanism.