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 WalMart.) 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 polynomialtime hierarchy in 1973. Michael Sipser's work (with Furst and Saxe) established the first superpolynomial lower bounds on boundeddepth 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, nearterm practical applications, and longrange speculative research. 

LearningAugmented Algorithms In recent years there has been increasing interest in using machine learning to improve the performance of classical algorithms in computer science, by finetuning 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 

MultiAgent 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 subgroups 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 systemslike 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: 