Theory of Computation (TOC) studies the fundamental strengths and limits of computation, how these strengths and limits interact with computer science and mathematics, and how they manifest themselves in society, biology, and the physical world.
At its core, TOC investigates tradeoffs among basic computational resources. These resources include computation time, space, communication, parallelization, randomness, quantum entanglement, and more. As computational systems come in many forms and the goals of computation are diverse, TOC studies the limits of computation in its many manifestations. These are determined by what access we have to the computation’s input: do we have access to it as a whole, or does it come as a stream; as samples from a distribution; in encrypted form; or in fragments? Limits are also determined by the environment within which the computation takes place. Beyond the architecture and connectivity of the computational environment determining where the data is produced and stored and where the computation takes place, we are interested in the presence of other forces, such as adversaries who might want to eavesdrop on the computation, or strategic parties who want to influence the computation to their benefit.
Moreover, computation takes place both in systems that are explicitly computational but also systems that are not explicitly computational, such as biological systems, the human brain, social networks, and physical systems. As such, TOC provides a scientific lens with which to study such systems, and the study of these systems motivates new models of computation and computational tradeoffs, to be studied in turn by TOC.
MIT’s TOC faculty research an unusually broad spectrum of both core TOC and interdisciplinary topics, including algorithms, optimization, complexity theory, parallel and distributed computing, cryptography, computational economics and game theory, computational algebra and number theory, computational geometry, quantum computation, computational biology, machine learning, statistics, and numerical computation.
Latest news in theory of computation
Six distinguished scientists with ties to MIT were recognized “for significant contributions in areas including cybersecurity, human-computer interaction, mobile computing, and recommender systems among many other areas.”
Mohammad Alizadeh has been named the Industry Officer for MIT’s Department of Electrical Engineering and Computer Science. In this role, Alizadeh will oversee the EECS Alliance, the department’s industry…
The Department of Electrical Engineering and Computer Science (EECS) recently announced the following crop of chair appointments, all effective July 1, 2022. Karl Berggren has been named the…
Guy Bresler builds mathematical models to understand multifaceted, interdisciplinary engineering problems that have far-reaching applications.
“Kids are people too!” Throughout his career, Professor Hal Abelson has worked to make information technology more accessible to people of all ages.
Professor Hal Abelson has dedicated his career to making information technology more accessible to all and empowering people — kids, in particular — through computer science. But his…