Theory of computation involves the use of powerful mathematical tools to obtain deep insights into fundamental problems of computation. Not being constrained by the current state of technology, research in this area is free to explore both ‘what is imaginable’ as well as ‘what is.’
At Yale theory research is concentrated in the areas of discrete mathematics, complexity theory, algorithms, learning, security, and distributed computing. Complexity theory looks at the relation between algorithm and computing device and attempts to determine the inherent difficulty of a computational task. Algorithms involves the invention and analysis of algorithms for sequential and parallel models of computation. Security is the field of computer science that looks at the reliability, privacy, and availability properties of information systems; it is intimately connected to several areas of theory, including algorithms, complexity theory, cryptography, and randomness. Distributed computing extends the domain of computation to encompass uncertainty and unreliability.
Two concepts that are fundamental to all areas of computer science are computing devices and algorithms. A computing device may be a computer, a network of computers, a circuit, a robot, or a software simulator or interpreter. An algorithm is a precise description of how some task is to be executed by a computing device. The curriculum in theory of computation is designed to provide a solid theoretical basis for the understanding of computing devices and algorithms.
The most important tool for this kind of theoretical understanding is ‘appropriate abstraction.’ The idea is to make a theoretical model of (for example) a computer that ignores enough of the details of any specific computer to be general, but is still specific enough that the theorems proved about it give useful insight into the capabilities of actual computers. The ability to use various levels of abstraction, from the immediately practical to the quite theoretical, is a lasting benefit of an education in computer science.
There is considerable contact with discrete mathematics, graph theory, number theory, mathematical logic, probability and statistics, operations research, economics, computational finance, and other related areas of study.
Faculty working in this area are Dana Angluin, James Aspnes, Joan Feigenbaum, Michael Fischer, Ravi Kannan, and Daniel Spielman.