Theory of Computation (TOC) Group

Theory of Computation (TOC) has undergone a number of evolutions in a short span of time. From its beginning in the 1960s as an outgrowth of mathematical logic and information theory, it evolved into a branch of mathematics where one looks at classical problems with the aesthetics of computational complexity and asks new questions concerning non-determinism, randomness, approximation, interaction, and locality. It then took a foundational role in addressing challenges arising in computer systems and networks, such as error-free communication, cryptography, routing, and search, and is now a rising force in the sciences: exact, life, and social. The TOC group at MIT has played a leadership role in theoretical computer science since its very beginning. Today, research done at the TOC group covers an unusually broad spectrum of research topics.

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 maintains a core of fundamental ideas and problems such as the famous P vs. NP problem or speeding up algorithms for traditional problems in graph theory, algebra, and geometry. But as the last two questions above suggest, TOC has increasingly been branching out, applying its intellectual toolkit to biology, economics, physics, and many other fields. Furthermore, TOC researchers pursue timely questions such as suggesting novel approaches to tackle the massive amounts of data that are collectable using today’s scientific techniques but cannot be harnessed by straightforward computing power; building reliable sensor networks out of unreliable components; and designing protocols for secure electronic voting.

Despite (or perhaps because of) its remove from immediate practical concerns, TOC has had a decisive impact on the development of real computer technology. The invention of the RSA public-key cryptosystem, by Ron Rivest, Adi Shamir, and Len Adleman in 1976 at MIT, 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, which handles about 15 percent of all traffic on the Internet.

MIT AND TOC: MIT has played a leadership role in theoretical computer science since its very beginning. The MIT TOC group is part of the Computer Science and Artificial Intelligence Laboratory (CSAIL) and spans two departments. It is comprised of faculty from Electrical Engineering and Computer Science and from Mathematics. This structure forms an immediate bridge between computer science (CS) and math. Indeed, the MIT Mathematics Department has been a pioneer in embracing TOC as a branch of applied mathematics for well over 30 years. Even earlier, Norbert Wiener and Claude Shannon were Mathematics Department faculty with clear interests in computation.

The current members of the TOC group have made contributions that have determined the course of TOC research for decades. Such “high impact” results include the RSA public-key cryptosystem, the pseudo randomness from hardness paradigm, the first super-polynomial size lower bound for a natural class of Boolean circuits, the impossibility of asynchronous consensus, zero-knowledge interactive proofs, quantum polynomial-time factoring, the connection between hardness of approximation and probabilistically checkable proofs, pioneering the use of semi-definite programming in approximation, expander codes, efficient list decoding, graph sparsifiers, cache-oblivious algorithms, the launch of algebraic and combinatorial property testing, locally sensitive hashing, a polynomial-time simplex method for linear programming, and a theory of asynchronous computability based on Topology. Several faculty members have created high-impact technology, founding companies such as RSA Data Security and Akamai, building on theoretical research. For their work, TOC faculty members and TOC students have received much recognition.

The MIT TOC faculty’s research covers an unusually broad spectrum of both core TOC and interdisciplinary topics, including distributed computing, parallel computing, networks, cryptography, algorithms, complexity theory, computational economics and game theory, computational algebra and number theory, computational geometry, quantum computation, computational biology, combinatorial optimization, and numerical computation. Indeed, the TOC group is divided into smaller research groups whose descriptions are included here.