Theory of Computation: Please see our new website here

Theory of Computation (TOC) is the study of the inherent capabilities and limitations of computers: not just the computers of today, but any computers that could ever be built. By its nature, the subject is close to mathematics, with progress made by conjectures, theorems, and proofs. What sets TOC apart, however, is its goal of understanding computation -- not only as a tool but as a fundamental phenomenon in its own right.

At MIT, we are interested in a broad range of TOC topics, including algorithms, complexity theory, cryptography, distributed computing, computational geometry, computational biology, and quantum computing.

What TOC Is About

The following questions, while not exhaustive, illustrate what theoretical computer scientists are interested in:

  • How do the resources needed to solve a computational problem (such as time, space, communication, and number of processors) scale with the size of the problem?
  • If a problem is intractable, can we at least find approximate solutions in a reasonable amount of time?
  • Can we distinguish "truly" random numbers from random-looking numbers generated by deterministic means? Is true randomness even necessary?
  • Can we build secure cryptographic protocols -- not just for exchanging secret messages, but for many other tasks needed in modern electronic commerce?
  • How can distributed agents reach a consensus, even in the presence of faults and malicious interference?
  • What sorts of computations can be carried out collectively by neurons in a brain, or proteins in a cell, or buyers and sellers in a marketplace?
  • What are the capabilities and limits of quantum computers?

As the last two questions suggest, TOC has increasingly been branching out, applying its intellectual toolkit to biology, economics, physics, and many other fields. But at the same time, it has also maintained a core of fundamental ideas and problems of its own.

TOC's most notorious open problem is called P versus NP. This is a problem that has withstood attack since the dawn of the computer age, that has clear and staggering practical implications, and that the Clay Mathematics Institute has recognized as one of seven great mathematical challenges of the millennium. Informally, the problem asks whether there exist puzzles for which a computer can easily recognize a solution, yet cannot find a solution without trying an astronomical number of possibilities. Based on experience, it seems obvious that such puzzles exist: think of scheduling airline flights, or piecing together a jigsaw puzzle, or breaking cryptographic codes, or for that matter solving mathematical problems like P versus NP itself! Yet after fifty years of research, no one can has been able to rule out the possibility of a "magic bullet" that would solve all of these problems and more, in barely more time than is needed to write them down. Over the last few decades, TOC has at least made a great deal of progress in understanding why this problem is so difficult, and in solving easier versions of it.

Despite (or perhaps because of) its remove from immediate practical concerns, TOC has had a decisive impact on the development of real computer technology. In the 1930's, Alan Turing's proof of the unsolvability of the Hilbert Entscheidungsproblem led him to discover the basic concepts, such as universality, that underlie all modern computer systems. Here at MIT, the invention of the RSA public-key cryptosystem, by Ron Rivest, Adi Shamir, and Len Adleman in 1976, provided an essential foundation for secure electronic commerce, without which, for example, Amazon and eBay could not exist. More recently, the study of efficient algorithms for routing data through networks, by MIT's Tom Leighton and Daniel Lewin, led to the creation of Akamai, a company that now handles about 15 percent of all traffic on the Internet.

In recent years, many TOC researchers have taken an interest in using the link structure of the Web and social networking sites to infer information about community; mining massive data sets for statistical information while still protecting individual privacy; building reliable sensor networks out of unreliable components; designing protocols for secure electronic voting; and applying "algorithmic thinking" to current problems in bioinformatics, statistical physics, and other sciences. As with any basic research, though, it is much easier to point to past successes than to predict what the next great application of TOC insights will be.

MIT has the largest TOC research group in the world. By following the links below, you can learn more about what we do...

The Cryptography and Information Security (CIS) research group is jointly led by Professors Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest.

How can mathematics and proofs contribute to the security of our computing infrastructure? What are the ``right'' models for computation and communication in the presence of adversaries? What the minimal assumptions about the computational difficulty of solving certain problems are required to achieve specified cryptographic objectives? Similarly, what minimal assumptions about the underlying hardware platform are needed? How does one design cryptographic primitives (like cryptographic hash functions) to be both efficient and secure? How do number theory, ellipitic curves, and lattices help provide security? How does cryptography relate to other areas such as computational complexity, error-correction, game theory, or quantum computation? How can cryptography be used to provide anonymous credentials, secure email, or universally verifiable voting?

These are but a few of the questions that have been addressed by the CIS group, which has a long history of major developments in both the theoretical and the practical aspects of cryptography and information security.

Theory of Distributed Systems (TDS). The Theory of Distributed Systems group, led by Prof. Nancy Lynch, works on a wide range of problems in distributed computing theory. Much of our work studies algorithms and lower bounds for typical problems that arise in distributed systems---like resource allocation, implementing shared memory abstractions, and reliable communication. Until recently, the focus was on rather static wired systems (see Lynch's book on Distributed Algorithms). However, in the past few years, most of our work has been on dynamic systems, in which the participants may come and go. We are now especially interested in wireless mobile ad hoc networks. In mobile networks, one wants to solve many of the same problems as in wired networks; however, new problems arise (e.g., getting messages to a particular geographical location, or controlling robots or cars), and new powers can be assumed (e.g., a node may know its approximate location). These new considerations provide interesting challenges for theoretical work.

The Computation and Biology group, led by Prof. Bonnie Berger, works on a number of problems at the interface of algorithms and biology. Many of the advances in modern biology revolve around recent advances in automated data collection and the subsequent large data sets drawn from them. We design algorithms to gain biological insights from this data and from future sources. We work on a diverse set of problems, including Protein Folding, Network Inference, Genomics, and Disease Classification. Additionally, we collaborate closely with biologists implementing these new techniques in order to design experiments to maximally leverage the power of computation for biological explorations.

Quantum Information. In 1994, CSAIL member Peter Shor showed that quantum computers, if built, would be able to break most of the cryptographic codes used in modern electronic commerce. This result played a central role in launching quantum computing and information as a field of study. Today Shor works on a variety of topics in quantum information theory and quantum algorithms. Scott Aaronson's research focuses on the limits of quantum computers, and more generally, on the interface between computational complexity theory and physics.

Computational Complexity. CSAIL members have done foundational work in computational complexity theory. Together with Larry Stockmeyer, Albert Meyer defined the polynomial-time hierarchy in 1973, while Michael Sipser has worked on circuit lower bounds, interactive proofs, and probabilistic computation. Jointly and in a number of collaborations Silvio Micali and Shafi Goldwasser discovered zero-knowledge interactive proofs (with Rackoff) in the 1980's; followed by mutli-prover inteactive proofs and their connection to inapproximability of HP-hard problems. They both continue to work on the foundations of cryptography. Madhu Sudan was one of the discoverers of the PCP Theorem, which led to the modern theory of inapproximability; he now works at the intersection of computational complexity and information theory. Ronitt Rubinfeld is one of the founders of the field of program checking and together with Sudan and Goldwasser the field of property testing, while Scott Aaronson is interested in quantum complexity theory and in barriers to solving P versus NP and related problems.

Parallel computing. Today's computers all contain multiple processing cores, and the number of processors per chip is expected to grow to hundreds or even thousands. How should these multicore chips be organized and interconnected? How should they be programmed? How should complex applications be solved in parallel? MIT's Theory of Computing group has long been leaders in providing answers to these fundamental questions that are built on theoretically solid foundations and grounded in provably correct and efficient algorithms. MIT research from the 1980's on VLSI theory and supercomputing led to hardware-efficient universal networks commonly used in computing clusters today, and it drove the technology of data-parallel computing. MIT research from the early 1990's on message-routing technology led to today's efficient content-delivery overlay networks on the Internet. MIT research from the middle 1990's on led to the provably good "work-stealing" schedulers used today in many multithreaded programming systems. MIT research from the late 1990's produced the technology of efficient "cache-oblivious" algorithms which use cache hierarchies near optimally without any tuning parameters. MIT research from the past few years promises provably efficient transactional-memory architectures, cache-consistency protocols for "networks on a chip," and parallel algorithms for unstructured problems. CSAIL faculty working on theory of parallel systems include Prof. Alan Edelman, who devised numerous parallel algorithms for numerical linear algebra and is father of the MATLAB*P programming environment; Dr. Bradley C. Kuszmaul, who devised a provably efficient superscalar processor, developed cache-oblivious disk file systems, and designed the first virtualized transactional memory system; Prof. Tom Leighton, who pioneered VLSI theory and content-delivery networks, discovered provably good algorithms for message routing, and devised work-preserving emulations of fixed-connection networks; Prof. Charles E. Leiserson, who invented systolic arrays, the retiming method for digital-circuit optimization, the fat-tree interconnection network, and cache-oblivious algorithms and who led development of the Cilk multithreaded programming language; and Prof. Nir Shavit who invented counting networks, software transactional memory, and the topological approach to asychronous computability.

Why Algorithms. In recent years, the amount of data on which computers are expected to operate has increased by several orders of magnitude, and it is no longer rare to come across data sets whose sizes are many terabytes. (Consider, for example, how one would use a computer to answer questions about the Internet, the human genome, or the sales logs of Wal-Mart.) Furthermore, we are asking computers to perform more and more intricate analyses on this data, requiring them to answer such diverse questions as calculating the 3-dimensional shape of a protein made up of many thousands of atoms, finding the most relevant web page to a query out of a pool of billions, or figuring out how best to allocate scarce resources among thousands of entities given only error-prone probabilistic information about the consequences of your decision. As the scope, difficulty, and importance of the problems that we pose to computers grow, it is crucially important that we devise new mathematical tools to attack them. The Algorithms group at MIT has long been at the forefront of this effort, with faculty ranking among the world experts in optimization, network algorithms, computational geometry, distributed computing, algorithms for massive data sets, parallel computing, computational biology, and scientific computing.



 MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
 The Stata Center, Building 32 * 32 Vassar Street * Cambridge, MA 02139 * USA