Theoretical computer science (TCS) is a division or subset of general
computer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
which focuses on more abstract or mathematical aspects of computing.
These divisions and subsets include
analysis of algorithmsTo analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
and
formal semantics of programming languagesIn programming language theory, semantics is the field concerned with the rigorous mathematical study of the meaning of programming languages and models of computation...
. Technically, there are hundreds of divisions and subsets besides these two. Each of the multiple parts have their own individual personal leaders (of popularity) and there are many associations and professional social groups and publications of distinction.
Scope
It is not easy to circumscribe the theory areas precisely and the
ACMThe Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
's Special Interest Group on Algorithms and Computation Theory (SIGACT) describes its mission as the promotion of theoretical computer science and notes:
To this list, the ACM's journal Transactions on Computation Theory adds
coding theoryCoding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
,
computational learning theoryIn theoretical computer science, computational learning theory is a mathematical field related to the analysis of machine learning algorithms.-Overview:Theoretical results in machine learning mainly deal with a type of...
and theoretical computer science aspects of areas such as databases,
information retrievalInformation retrieval is the area of study concerned with searching for documents, for information within documents, and for metadata about documents, as well as that of searching structured storage, relational databases, and the World Wide Web...
, economic models and
networksA computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
. Despite this broad scope, the "theory people" in computer science self-identify as different from the "applied people." Some characterize themselves as doing the "(more fundamental) 'science(s)' underlying the field of computing." Other "theory-applied people" suggest that it is impossible to separate theory and application. This means, the so called "theory people" regularly use experimental science(s) done in less-theoretical areas such as
software systemA software system is a system based on software forming part of a computer system . The term "software system" is often used as a synonym of computer program or software; is related to the application of systems theory approaches in software engineering context and are used to study large and...
research. This also means, there is more cooperation than mutually exclusive competition between theory and application.
 |
 |
 |
 |
| Mathematical logic Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
|
Automata theory In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
|
Number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
|
Graph theory In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
|
 |
 |
 |
 |
| Type theory In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
|
Category theory Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
|
Computational geometry Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
|
Quantum computing theory A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
|
History
While formal algorithms have existed for millennia (Euclid's algorithm for determining the
greatest common divisorIn mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
of two numbers is still used in computation), it was not until 1936 that
Alan TuringAlan Mathison Turing, OBE, FRS , was an English mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in the development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing machine, which played a...
,
Alonzo ChurchAlonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
and Stephen Kleene formalized the definition of an algorithm in terms of computation. While binary and logical systems of mathematics had existed before 1703, when
Gottfried LeibnizGottfried Wilhelm Leibniz was a German philosopher and mathematician. He wrote in different languages, primarily in Latin , French and German ....
formalized logic with binary values for
true and
false. While logical inference and mathematical proof had existed in ancient times, in 1931
Kurt GödelKurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
proved with his incompleteness theorem that there were fundamental limitations on what statements, even if true, could be proved.
These developments have led to the modern study of logic and computability, and indeed the field of theoretical computer science as a whole.
Information theoryInformation theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
was added to the field with a 1948 theory of the statistical mechanics of information by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of
neural networkThe term neural network was traditionally used to refer to a network or circuit of biological neurons. The modern usage of the term often refers to artificial neural networks, which are composed of artificial neurons or nodes...
s and parallel distributed processing were established.
With the development of
quantum mechanicsQuantum mechanics, also known as quantum physics or quantum theory, is a branch of physics providing a mathematical description of much of the dual particle-like and wave-like behavior and interactions of energy and matter. It departs from classical mechanics primarily at the atomic and subatomic...
in the beginning of the 20th century came the concept that mathematical operations could be performed on an entire particle wavefunction. In other words, one could compute functions on multiple states simultaneously. This led to the concept of a
quantum computerA quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
in the latter half of the 20th century that took off in the 1990s when
Peter ShorPeter Williston Shor is an American professor of applied mathematics at MIT, most famous for his work on quantum computation, in particular for devising Shor's algorithm, a quantum algorithm for factoring exponentially faster than the best currently-known algorithm running on a classical...
showed that such methods could be used to factor large numbers in polynomial time, which, if implemented, would render most modern public key cryptography systems uselessly insecure.
Modern theoretical computer science research is based on these basic developments, but includes many other mathematical and interdisciplinary problems that have been posed.
Journals and newsletters
- Information and Computation
Information and Computation is a computer science journal published by Elsevier . The journal was founded in 1957 under its former name Information and Control. The editor-in-chief is A.R. Meyer...
- Theory of Computing
Theory of Computing is an online open access journal dedicated to theoretical computer science. The journal was founded in 2005 amidst growing concerns about the financial difficulties of university libraries around the world faced with rising costs in subscriptions to scientific journals owned by...
(open access journal)
- Formal Aspects of Computing
Formal Aspects of Computing is a peer-reviewed scientific journal published by Springer Science+Business Media, covering the area of formal methods and associated topics in computer science. The editors-in-chief are Jim Woodcock and Cliff Jones. The journal is associated with BCS-FACS, the British...
- Journal of the ACM
The Journal of the ACM is the flagship scientific journal of the Association for Computing Machinery . It is peer-reviewed and covers computer science in general, especially theoretical aspects. Its current editor-in-chief is Victor Vianu, from University of California, San Diego.The journal has...
- SIAM Journal on Computing
The SIAM Journal on Computing is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics . As of September 2008, Éva Tardos serves as editor-in-chief.-External links:** on DBLP...
(SICOMP)
- SIGACT News
- Theoretical Computer Science
Theoretical Computer Science is a computer science journal published by Elsevier, started in 1975 and covering theoretical computer science. The journal publishes 52 issues a year. It is abstracted and indexed by Scopus and the Science Citation Index...
- Theory of Computings Systems
- International Journal of Foundations of Computer Science
The International Journal of Foundations of Computer Science is a computer science journal published by World Scientific. It was founded in 1990, covering the field of theoretical computer science, from algebraic theory and algorithms, to quantum computing and wireless networks...
- Chicago Journal of Theoretical Computer Science (open access journal)
- Foundations and Trends in Theoretical Computer Science
- Journal of Automata, Languages and Combinatorics
The Journal of Automata, Languages and Combinatorics is a peer-reviewed scientific journal of computer science, edited by Jürgen Dassow. It was established in 1965 as the Journal of Information Processing and Cybernetics/Elektronische Informationsverarbeitung und Kybernetik and obtained its current...
- Acta Informatica
Acta Informatica is a peer-reviewed scientific journal publishing original research papers in computer science.The journal is known mostly for publications in theoretical computer science. One of the two 1988 papers awarded the Gödel Prize in 1995 has appeared in this journal....
- Fundamenta Informaticae
The academic journal Fundamenta Informaticae is a computer science journal edited by Andrzej Skowron . It was launched in 1977 by the Polish Mathematical Society as Series IV of the annals "Annales Societatis Mathematicae Polonae", with its main focus on theoretical foundations of computer science...
- ACM Transactions on Computation Theory
- ACM Transactions on Algorithms
- Information Processing Letters
Conferences
- Annual ACM Symposium on Theory of Computing
STOC, the Annual ACM Symposium on Theory of Computing is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computer Machinery special interest group SIGACT.As...
(STOC)
- Annual IEEE Symposium on Foundations of Computer Science
FOCS, the Annual IEEE Symposium on Foundations of Computer Science, is an academic conference in the field of theoretical computer science...
(FOCS)
- ACM–SIAM Symposium on Discrete Algorithms (SODA)
- Annual ACM Symposium on Computational Geometry
The Annual Symposium on Computational Geometry is an academic conference in computational geometry. It was founded in 1985, and in most but not all of its years it has been sponsored by the Association for Computing Machinery's SIGACT and SIGGRAPH special interest groups.A 2010 assessment of...
(SoCG)
- International Colloquium on Automata, Languages and Programming
ICALP, the International Colloquium on Automata, Languages and Programming is an academic conference organized annually by the European Association for Theoretical Computer Science and held in different locations around Europe...
(ICALP)
- Symposium on Theoretical Aspects of Computer Science (STACS)
- European Symposium on Algorithms
The European Symposium on Algorithms is an international conference covering the field of algorithms. It has been held annually since 1993, typically in a different European location in early Autumn...
(ESA)
- IEEE Symposium on Logic in Computer Science (LICS)
- International Symposium on Algorithms and Computation (ISAAC)
- Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
- Workshop on Randomization and Computation (RANDOM)
- Computational Complexity Conference (CCC)
- ACM Symposium on Parallelism in Algorithms and Architectures
SPAA, the ACM Symposium on Parallelism in Algorithms and Architectures, is an academic conference in the fields of parallel computing and distributed computing...
(SPAA)
- ACM Symposium on Principles of Distributed Computing
The Symposium on Principles of Distributed Computing is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery ....
(PODC)
See also
Further reading
- Martin Davis
Martin David Davis, is an American mathematician, known for his work on Hilbert's tenth problem . He received his Ph.D. from Princeton University in 1950, where his adviser was Alonzo Church . He is Professor Emeritus at New York University. He is the co-inventor of the Davis-Putnam and the DPLL...
, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science, 2nd ed., Academic Press, 1994, ISBN 0122063821. Covers theory of computationIn theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
, but also program semantics and quantification theory. Aimed at graduate students.
External links