Research in theoretical computer science has been supported by both the federal government and industry. Almost without exception in the cases discussed, contributions from U.S. academia acknowledge the support of federal agencies, most notably the NSF and ONR. Nevertheless, many advances in theoretical computer science have emerged from major industrial research laboratories, such as IBM, AT&T (Bell Laboratories), and GE. This is partly because some of the areas examined developed before the NSF was established, but also because some large corporate laboratories have provided an environment that allows industry researchers to produce directly relevant results while also carrying on long-term, theoretical investigations in the background. Shannon, for example, apparently worked on information theory for a decade before he told the world about it.
Theoretical computer science has made important contributions to computing practice while, conversely, also being informed by that practice. Work on the theory of one-way functions, for example, led to the development of public-key cryptography, and the development of complexity theory, such as Cook's conjecture, sparked efforts to improve methods for approximating solutions to nondeterministically tractable problems. Similarly, the theoretical work in complexity and program correctness (or verification) has been redirected by the advancing needs of computing systems.
Academia has played a key role in propagating computing theory. By teaching and writing textbooks, academic researchers naturally influenced the subjects taught, especially during the formative years of computer science departments. However, some important synthesizing books have come from industrial research laboratories, where management has seen fit to support such writing to enhance prestige, attract candidates, and foster the competence on which research depends.
Foreign nations have contributed to theoretical computer science. Although the United States has been the center of systems-related research, a considerable share of the mathematical underpinnings for computer science can be attributed to British, Canadian, and European academics. (The wider practical implementation of this work in the United States may be explained by a historically greater availability of computers.) The major foreign contributions examined in this case were all supported by governments; none came from foreign industry.
Personal and personnel dynamics have also played important roles. Several of the papers cited in this chapter deal with work that originated during the authors' visiting or short-term appointments, when they were free of the ancillary burdens associated with permanent positions. Research-