Research in the Theoretical and Algorithmic Foundations of Computing
Are there problems that simply cannot be solved by a computer algorithm? If so, what are they, and why is this so? For the problems that can be solved, how efficiently (in terms of time, memory, or communications requirements) can this be done? And for those that can’t be solved, can we make practical use of this fact, for example, to help ensure better privacy on our computer systems?
These are some of the most basic questions in computing. Research to address such questions is often motivated by the desire to understand the basic nature of computation rather than to find practical applications. However, time and again discoveries are made that provide new ways to solve difficult algorithmic problems. For example, research in coding theory, which investigates the fundamental limits in the encoding and decoding of messages, has led to methods for transmitting messages in ways that are highly tolerant of faulty communications channels, and ultimately to methods that achieve very close to the maximum possible efficiency and provide a foundation for nearly all of today’s wireless technologies, ranging from mobile phones, to WiFi, to deep-space communications.
The impact of theoretical and algorithmic research is wide-ranging. Algorithms for network congestion provide the key building block for today’s content-distribution networks. Modern logistics systems, such as those used by the airline industry or package delivery systems, depend on a deep understanding of the limits of computation and algorithms for optimal allocation of resources and for scheduling. All modern search engines make use of fundamental knowledge of how mathematical concepts such as eigenvalues can be used to rank Web pages. All electronic commerce today is built on foundational concepts of so-called one-way functions, developed in some of the most theoretical computing research endeavors. And today’s speech and natural language understanding systems apply large-scale statistical analysis algorithms in sophisticated ways.
Additional examples of the impacts from algorithms research are provided in Appendix C.
Although the tracks in Figure 1 were chosen to illustrate through prominent examples how each selected research area is connected with a closely linked industry area, in reality each research area is linked in many ways to one or more industry areas. Research outcomes in one area have continued to affect and enable research in other areas. Furthermore, synergies among research areas often lead to surprising results and have impacts on industry that were not originally intended or envisioned (Table 2). This characteristic of technological innovation is most evident in the broad-based impact of research on basic questions in computing. Such research often starts as a search for fundamental knowledge but time and again produces practical technologies that enable significant economic impact, in areas as diverse as optimal resource allocation and scheduling, compact encodings of signals, efficient search algorithms, fair auction and voting mechanisms, and ultralarge-scale statistical analyses. (Box 1 provides further discussion.)
The arrows between the vertical tracks represent some salient examples of the rich interplay between academic research, industry research, and products and indicate the cross-fertilization resulting from multi-directional flows of ideas, technologies, and people (examples are given in Appendix B). Also illustrated in Figure 1 is how products arising from industry can shape academic research. (For example, Microsoft’s Kinect sensor is now being used in many research applications, and Google’s practical application of MapReduce introduced new ideas about web-scale distributed computing to the research community.) Arrows spanning research areas provide a few indications of the interdependence of research advances in various areas.