Theoretical computer science

# Theoretical computer science

Overview
Theoretical computer science (TCS) is a division or subset of general computer science
Computer science
Computer 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 mathematics
Mathematics
Mathematics 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.
Discussion
 Ask a question about 'Theoretical computer science' Start a new discussion about 'Theoretical computer science' Answer questions from other users Full Discussion Forum

Encyclopedia
Theoretical computer science (TCS) is a division or subset of general computer science
Computer science
Computer 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 mathematics
Mathematics
Mathematics 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 algorithms
Analysis of algorithms
To 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 languages
Formal semantics of programming languages
In 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 ACM
Association for Computing Machinery
The 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 theory
Coding theory
Coding 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 theory
Computational learning theory
In 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 retrieval
Information retrieval
Information 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 networks
Computer network
A 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 system
Software system
A 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 logicMathematical logicMathematical 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 theoryAutomata theoryIn 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 theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well... Graph theoryGraph theoryIn 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 theoryType theoryIn 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 theoryCategory theoryCategory 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 geometryComputational geometryComputational 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 theoryQuantum 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...

## History

While formal algorithms have existed for millennia (Euclid's algorithm for determining the greatest common divisor
Greatest common divisor
In 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 Turing
Alan Turing
Alan 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 Church
Alonzo Church
Alonzo 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 Leibniz
Gottfried Leibniz
Gottfried 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ödel
Kurt Gödel
Kurt 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 theory
Information theory
Information 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 network
Neural network
The 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 mechanics
Quantum mechanics
Quantum 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 computer
Quantum computer
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...

in the latter half of the 20th century that took off in the 1990s when Peter Shor
Peter Shor
Peter 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.

• Information and Computation
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 (journal)
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
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
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
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 (journal)
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
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
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
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
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
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
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
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
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
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
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
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)