on relations between theoretical computer science and the other sciences

See the disclaimer on the previous page.

  • Dealing with discrete objects, 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 wealthy 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 draw 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 like an object exists with the problem how efficiently can this object be constructed?  Trying to answer them typically reveals more structural questions, and a combination of math and algorithmic theoretical computer science techniques have significantly transformed such attitudes (which of course go back to Hilbert and even to Euclid) into 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 the problems they are interested in. For the well defined problems 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 in which the required output is not "well defined in advance'' are challenging theoretical computer science. 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

Sponsored by:

National Science Foundation

State of New Jersey 		Abacus

Abacus 		Analytical engine by Charles Babbage

"Analytical Engine"

by Charles Babbage 		Turing Machine

Turing Machine