Summary of Theory of Computation: Goals and Directions

Alfred V Aho, David S Johnson, Richard M Karp, S Rao Kosaraju, Catherine C. McGeoch, Christos H Papadimitriou, Pavel Pevzner

The full report is available as a compressed Postscript file via anonymous ftp at the following URL: ftp://ftp.cs.washington.edu/tr/1996/03/UW-CSE-96-03-03.PS.Z

1 Introduction

This report grew out of an NSF sponsored workshop, held on June 2, 1995 with the purpose of assessing the current goals and directions of the Theory of Computing (TOC) community and suggesting actions and initiatives to enhance the community's impact and productivity.

We discuss the history, current state, and future of theoretical research in CS from a global perspective, since the sense of community in theoretical CS transcends national boundaries. However, we recognize that the circumstances under which theoretical computer scientists are trained and the patterns of activity in theoretical CS research vary greatly from country to country. For this reason, our suggestions about graduate education and employment, and our recommendations about areas of emphasis and funding directions, are targeted specifically for research programs in the United States.

The committee found it useful to identify three distinct (although heavily interacting and overlapping) types of research activity within TOC.

Core theory

This field studies computation as an abstract phenomenon. In recent years, research in core theory has resulted in notable and largely unexpected developments in areas such as cryptography, computational learning, ... parallel and distributed computation, ... Core theory has achieved a remarkable unity, in which seemingly unrelated topics are found to have surprising connections and to be amenable to investigation by common mathematical techniques.

Fundamental algorithms

This field uses sophisticated mathematical techniques to develop solutions to problems that transcend application domains. This area includes such central topics as combinatorial algorithms, approximation algorithms, ... , data structures for search, graph operations, ... .

Application-specific theory

This area deals with computational phenomena arising in application areas. The Human Genome Project is an example of such an application area. This area of research has not flourished to the same extent as core theory and fundamental algorithms. This is largely due to the fact that the TOC community places excessive weight on mathematical depth and elegance and attaches too little importance to genuine links between theory and concrete applications. The neglect of application-specific theory is largely responsible for the general CS community's failure to appreciate contemporary theoretical research.

Our recommendations are largely based on the following fundamental point: In order for TOC to prosper in coming years, it is essential to strengthen our communication with the rest of CS and with other disciplines, and to increase our impact on key application areas. If we do so, then funding will flow to TOC from a variety of sources. If instead we turn inward then our chances of adequate funding and employment opportunities will be compromised. Our broad recommendations for the future development of TOC fall into four main categories: building bridges between theory and applications, algorithm engineering, communication and education.

Building bridges ...

There are many striking examples of TOC exerting an influence on applied fields --- algebraic algorithms for robot motion planning, complexity-theoretic results in cryptography for secure communication protocols etc. Such applied studies require theoreticians to cope with the messiness of the real world, often at the expense of elegance, mathematical depth and universality. Nevertheless, in order maximize its impact on the rest of CS, TOC researchers will have to put in the effort to carry a theoretical idea through to the point where it begins to have a practical impact.

Algorithm engineering

Within TOC, algorithms are usually studied within highly simplified models of computation and evaluated by metrics which are unlikely to predict actual performance. The TOC community must come to recognize that algorithm engineering --- the experimental testing and tuning of algorithms --- is integral to its mission.

Communication

We must explain to the rest of the CS community and others our past accomplishments, our present endeavors and our potential for outstanding future contributions. When we write papers, we should include realistic assessments of the applicability of our results.

Education

Graduate students in theoretical CS must develop an awareness of applications and experimental research. Otherwise they will have limited employment opportunities given the prevailing situation in the job market.

2 Achievements of Theoretical CS

This section briefly summarizes the achievements of TOC. The list of achievements includes the theory of parsing and compilation, NP-completeness, complexity theory of parallel computation, interactive proofs, ...

The following three achievements are discussed in some detail: Interior Point Algorithms in optimization, Relational Databases and NP-completeness.

3 Bridges to Applications: Some Promising Directions

This section suggests some possible future connections between TOC research and important application areas. We have selected areas where there is a good chance of attracting funds from new sources.

Theory of Software Construction

The demand for new software systems far outstrips our ability to construct them. Impressive advances in our theoretical understanding of programming language semantics, program correctness etc have not led to comparable advances in the pragmatic task of producing reliable software.

Computational Biology

At the heart of modern biology is a vast effort to acquire and interpret genetic information. This has introduced a need for new combinatorial algorithms and database techniques. At the same time, it has become fashionable to work in areas which sound biologically relevant but omit key aspects, such as the presence of errors in the data. Algorithm researchers should work with biologists to formulate and solve real problems.

Future Application Areas

Future funding efforts should be directed at research which addresses applications arising out of the spread of computers and communications, parallel and distributed systems and large knowledge repositories. In the next two sections, we propose two specific initiatives which focus theoretical research on these objectives.

4 Information Access in a Globally Distributed Environment

As computers and communication become ubiquitous, it should become possible for people wherever they are to find the information they need, in the media they desire, and in a form they can understand.

For this, we need to design new models and methods for organizing, storing, retrieving, processing and presenting multimedia information. We also need methods for ensuring appropriate levels of security, safety and privacy among users of highly interconnected resources.

5 The Algorithmic Tool Kit

Because software is not sufficiently portable or reusable, it is difficult for software designers to make use of the work of others, and a great deal of duplication of effort results. It is also clear that in many cases there is a considerable time lag between the discovery of a better algorithm for a problem and its implementation in application software (if indeed it is implemented at all!)

We propose building an Algorithmic Tool Kit --- a suite of portable and reusable software components. The initial set of building blocks would be implementations of fundamental data structures (heaps, trees, ... ) The next layer would include implementations of well-analyzed algorithms for sorting, searching, string manipulation ... At the next layer would be building blocks to support communication and data access in parallel and distributed environments (including algorithms for routing, communication protocols, security ...).

The Tool Kit would be freely accessible over the Internet. For the sake of reusability and portability, the algorithms would be specified at a machine-independent level. The choice of a specification language would be a major research challenge.

6 Education

Theory students face a lack of job opportunities after graduation. There is also a perception that theory students are less prepared for jobs in industry than students in other areas of CS. To remedy the problem and change the perception, graduate programs in CS must be shaped to meet two broad goals. First, all graduate students should be aware of both the potential and the limitations that both old and new theoretical results have for helping to solve applied problems. Second, young theoreticians must obtain greater exposure to practical research problems in CS and other disciplines.

Funding agencies can support efforts to broaden the education of theory students and strengthen the ties between theoreticians and practitioners as follows: