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.
