New Directions in CS Research

By John E. Savage

In its early history theoretical computer science research was strongly motivated by the problems of practice. When compilers were being invented, a framework was developed for the study of languages and their efficient translation. When large instances of problems were first being solved by computer, new algorithms and data structures were invented for them. Similarly, when problems were identified that did not seem to admit efficient algorithms, analysts developed methods to classify them by their complexity, identifying complexity classes such as the famous NP-complete languages in the process.

Traditionally experimental computer scientists identified an important computational problem that was not amenable to the modeling and analysis practiced by theoreticians, invented conceptual solutions, and then demonstrated their viability through proof of concept, that is, by building a system and studying its behavior through experimentation, measurement, and some analysis. Many important conceptual advances have resulted from this approach, advances that are reflected in the software, hardware, and communication technologies in use today.

Because computer science is now undergoing very rapid change, the early role of universities as the principal centers for the generation of knowledge and examples of new technologies is weakening. Important innovation is now occurring in development organizations out of sight of universities and research laboratories. As a consequence, important new problems and ideas are emerging that are not readily accessible to the research labs and the academic computer science community, and important opportunities are being lost to contribute to the application and development of these ideas and the solution of these problems.

The rapid development of computer science has introduced a new tension between innovation and the generation of knowledge. An important role has emerged for experimental academic computer scientists, namely, to work closely with industrial colleagues in order to understand and abstract from the large complex systems that they are building. A new opportunity is also emerging for theoreticians, namely, to work with their experimental computer science colleagues and industrial developers to study the deep and complex computational issues presented by the emerging new technologies.

New opportunities of this kind now exist to design, experiment with, model, and analyze the important computational problems encountered in building telecommunications networks, designing large software systems, data management and searching, planning, optimization, distributed computing, scientific computing, and many other areas. Some members of the academic and industrial research communities have discovered these opportunities and have obtained important results on topics such as secure cryptographic systems, web searching algorithms that identify authoritative sites, data caching algorithms that operate with much smaller queues, and scientific computing algorithms that more intelligently allocate work.

In the future we can expect many improvements in all aspects of computation through better modeling and analysis. We can expect the throughput of computer networks to be improved by studying the distribution of network traffic and developing better network management algorithms. Web-based applications will benefit greatly from modeling, experimentation, design, and analysis. Algorithms for large, compute-intensive tasks will allow scientists to perform much larger simulations of complex problems by focusing the computational work where it is needed. These and many other issues offer important opportunities for the academic and industrial research communities to advance our understanding of computation by refocusing our energies and talents on the challenging problems arising in the context of new applications. It is very much in the interest of the nation that the research funding agencies should support such interactions.

John Savage is a member of the computer science faculty at Brown University, a former member of the CRA Board of Directors, and the author of "Models of Computation," recently published by Addison Wesley. (See also www.cs.brown.edu/people/jes.)