Directions for Research

Computer science is a vibrant field, full of potential. Not only are new products emerging every day, the demands of the field create new computational problems that need solution, many of them highly complex. Since the computer scientist is needed when the computational problem is hard, this means that our field is likely to be in demand for the foreseable future.

Many areas offer problems of sufficient complexity and importance to warrant the attention of the theoretical computer scientist. Some of these currently lack the precision that usually attracts theoreticians but, through joint work with experimentalists, this can change.

A list of research areas that may attract theoreticians is given below. It is not intended to be complete nor the description of a research agenda. Our community is rich in diversity which should continue to be encouraged. Together we can come to agreement on areas that have high potential, bearing in mind, of course, that it is undesirable to invest too fully in too few areas, especially areas that have received a great deal of attention in the past.

• Parallel and distributed computing are increasing steadily in importance. Manufacturers now offer symmetric multiprocessors as well as support for locally and remotely distributed computing. The problems they encounter in coordinating activity, accessing data, securing transactions while achieving high performance are challenging.
• Many companies are now very dependent on high-performance computing for the simulation of complex designs and for the planning and scheduling of work of all kinds. These areas have profited and will continue to profit from the research of theoreticians.
• The growing complexity of software offers immense challenges to specification and understanding for which the talents of theoreticians are appropriate. This is an area in which interaction with experimentalists will lead to new methods for specifying and verifying software systems. Interestingly, while algorithms and data structures are important in the design of large complex software systems, they occupy a relatively small fraction of a designer's time.
• As computer systems become more complex, understanding their behavior and performance will present daunting challenges. This topic will increase in importance as the profit margins on computer systems shrink.
• Data storage and retrieval in the future will not be limited to relational and object oriented databases. Data in a large variety of formats and types will commingle and search and retrieval mechanisms will be invented to access them. Theoreticians can play a role here by laying the foundations for the logical development of this area.

Most traditional areas of computer science will continue to evolve and require the attention of theoretical computer scientists.

New areas will emerge that are hard to predict. For example, ubiquitous and mobile computing in which many users migrate their work and attention to different computers will offer many challenges including the obvious one of resource allocation. Quantum computing has the tantalizing prospect of being a new and highly parallel computing model that may be used to solve very hard problems in an instant.

Computer science is a thriving area that will continue to thrive for decades to come. The role for the theoretician in computer science is to create new computational models and to explore the power and limits of these models for important problems. As long as the computational problems are very hard there is a role for the theoretician.