See the disclaimer on the previous page.
- Questions from theoretical computer science inspired much interest in the combinatorics community, and for many of its leaders became a primary scientific goal. This collaboration has been extremely beneficial to both the discrete math and theoretical computer science communities, with healthy exchange of ideas, problems and techniques (see also Discrete Mathematics: Past, Present and Future).
- The mathematical challenges which arise from (mainly complexity) questions in theoretical computer science (see Special Year on Computational Complexity 2000-2001, topic page), seem to demand in certain cases the use of techniques in other branches of math, like algebra, topology and analysis, and these occurrences are becoming more frequent. More importantly, the fundamental problems of theoretical computer science, like the P vs. NP problem, have gained the appropriate prominence as central problems of mathematics, and drawn pure mathematicians to tackle them.
- It is extremely important that this conversation between mathematics and theoretical computer science is two-way. More and more mathematicians are considering "computational" aspects of their areas, following theorems establishing the existence of some objects with an investigation of the efficient constructibility of such objects. This approach (which has deep roots in the work of figures such as Euclid and Hilbert) typically reveals further structural questions, and a combination of math and algorithmic techniques have fostered active research areas like computational number theory, computational algebra and computational group theory.
- Scientists' use of computers has grown tremendously in the last two decades, mostly for the analysis of massive data sets. But the currently available resources of even the newest computer systems are far from being sufficient for solving all problems of interest. Efficient algorithms have yet to be (and are being) developed. Among these are e.g. the convergence analysis of some Monte Carlo algorithms used by statistical physicists, and the growing work on computational biology. Yet another exciting area of collaboration, where foundational work on theoretical computer science side goes hand-in-hand with experimental work in physics, is quantum computing.
- A whole new type of algorithmic problems from natural sciences are challenging theoretical computer science: namely, problems in which the required output is not "well defined in advance." Typical data might be a picture, a sonogram, readings from the Hubble Space Telescope, stock-market share values, DNA sequences, neuron recordings of animals reacting to stimuli, or any other sample of "natural phenomena". The algorithm (like the scientist), is "trying to make sense" of the data, "explain it", "predict future values of it", etc. The models, problems and algorithms here fall into the research area of computational learning and its extensions.
- Economics is also playing a growing role as a source of problems and paradigms for theoretical computer science, beyond the analysis and prediction of the stock market. Historically, economic and decision making problems initiated one of the first grand achievements in algorithm design - the simplex method (and its successors) for linear programming. But now the roles are reversed and economic theories are called to solve computer science problems, as multitudes of autonomous robots, or of independent programs on the Web, have to be programmed to function in adversarial (or at least selfish) environments, and best achieve their goals. Exciting beginnings of such models and solutions are now budding.
Some related external links and references
- O. Goldreich, A. Wigderson. Theory of Computation: A Scientific Perspective, an essay.
- A. Razborov. Theoretical Computer Science: a mathematician's look (Russian), full version of an essay written for Computerra.
- S. Smale. Mathematical Problems for the Next Century, Mathematical Intelligencer, 1998, vol. 20, #2, pages 7-15.