Research Groups | MIT CSAIL Theory of Computation

	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: