Research Groups

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... more

Computation and Biology

The Computation & Biology Group comprises members from the Department of Mathematics and EECS at the Massachusetts Institute of Technology (MIT), and the Theory of Computation group at the MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). The group focuses on various areas of research within the field of Computational Biology. More details concerning the group's recent... more

Complexity Theory

Many CSAIL members have done foundational work in computational complexity theory. Larry Stockmeyer and Albert R. Meyer worked together to define the polynomial-time hierarchy in 1973. Michael Sipser's work (with Furst and Saxe) established the first super-polynomial lower bounds on bounded-depth circuits, and the first derandomization in complexity classes by showing that BPP lies in the... more

Computation and Economics

Many systems have components that are controlled by people (as in the Internet) or are people themselves (as in an auction). Engineering such systems becomes more challenging, since each user may try to game them to his own advantage. This is even more true as the size of the system grows but the resources of the designer do not. How should one go about designing such systems? In particular... more

Computational Connectomics

Mapping the Structure of Thought.  Understanding the structure and function of the nervous system is an exceptionally complex task: the system consists of thousands of cells connected to thousands of other cells in microscopic networks that extend over large volumes and exhibit a seemingly endless variety of behaviors. We believe that mapping such networks at the level of synaptic connections... more

Cryptography and Information Security (CIS)

We seek to develop techniques for securing tomorrow's global information infrastracture by exploring theoretical foundations, near-term practical applications, and long-range speculative research.

We are also interested in the relationship of our field to others, such as complexity theory, quantum computing, algorithms, game theory, machine learning, and... more

Learning-Augmented Algorithms

In recent years there has been increasing interest in using machine learning to improve the performance of classical algorithms in computer science, by fine-tuning their behavior to adapt to the properties of the input distribution. Many applications involve processing streams of data (video, data logs, customer activity etc) by executing the same algorithm on an... more

Multi-Agent LearningMany learning settings involve multiple agents that learn and make decisions in a shared environment wherein rewards, observations, and state transitions are influenced by the collective decisions of all agents. These settings: 

- might be cooperative or antagonistic;
Parallel Computing

Parallel computing has become the dominant paradigm in computer architecture in recent years. The parallel computation group includes three sub-groups addressing the design of parallel software, from languages to algorithms and to the fields computational foundations.


* The Multicore algorithmics Group headed by Prof. Nir Shavit develops techniques for designing, implementing, and... more

Quantum Information Science

Quantum computing is a model of computation based on the laws of quantum mechanics. Quantum computers appear to be qualitatively more powerful than classical computers and have the potential to revolutionize cryptography as well as all areas of science that study complex quantum systems (e.g. physics, chemistry, biology). Research interests in the theory group include... more

Sublinear Algorithms

As the sizes of datasets grow to enormous proportions,  there is a need for analyzing data with sublinear constraints -- that is, for the design of algorithms which require only sublinear time, space, measurements and/or samples.   

Theory of Distributed Systems

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... more

Theory of Machine Learning

The Theory of Machine Learning group studies fundamental questions in learning theory and statistics, informed by perspectives grounded in algorithms, computational complexity, statistics, information theory, probability, statistical physics, and more. We are interested in questions such as: