#### Community of Research

# Theory of Computation Community of Research

The goal of the Theory of Computation CoR is to study the fundamental strengths and limits of computation as well as how these interact with mathematics, computer science, and other disciplines.

Also of interest are how these strengths and limitations manifest themselves in society, biology, and the physical world.

#### Related Links

##### Contact us

If you would like to contact us about our work, please refer to our members below and reach out to one of the group leads directly.

Last updated Mar 20 '23

#### Research Areas

#### Impact Areas

#### Related Links

## Members

## Projects

#### Project

## Eyebrowse: Social and Public Web Browsing

Eyebrowse aims to create a social outdoors for your web browsing.

#### Project

## Using Reductions to Understand Polynomial Time Algorithms

For many problems the best known algorithms take polynomial time but super linear time, we want to understand why problems like diameter, longest common sub-sequence and co-linear point detection can't be solved in linear time.

#### Project

## Mavo: Creating Interactive Data-Driven Web Applications by Authoring HTML

Mavo is a language that lets anyone turn a static HTML document into a fully functioning reactive web application with data presentation, editing, storage and lightweight computation, all without writing a single line of Javascript or other programming code.

## Lea Verou

#### Leads

## Lea Verou

#### Research Areas

#### Project

## Algebraic Techniques for Algorithm Design

We work on improving the algorithms for algebraic problems like matrix multiplication, and using these to design algorithms for fundamental non-algebraic problems.

#### Project

## Approximating the diameter of a directed graph

There is a family of approximation algorithms for computing the diameter of an undirected graph that give a time/accuracy trade-off and our goal is to extend these results to directed graphs.

#### Project

## Sketching Distances in Graphs

We try to come up with efficient ways to remove edges from graphs without changing the shortest path distance between any two nodes by very much.

#### Project

## Spatial Data Structure Parallel Merging

We are creating a concurrent data structure for 2D/3D points that supports efficient storage, range queries, and merging of disjoint datasets, motivated by highly-parallel algorithms for reconstructing neuron connections in the brain.

#### Project

## Sublinear/Streaming Algorithms for Covering Problem

Our goal is to develop efficient algorithms for the fundamental set cover problem in the massive data model.

#### Project

## Sublinear Algorithms for Massive Data Problems

This project includes designing efficient algorithms and proving lower bounds for fundamental problems under the models that address big data.

#### Project

## Basing Cryptography on Structured Hardness

We aim to base a variety of cryptographic primitives on complexity theoretic assumptions. We focus on the assumption that there exist highly structured problems --- admitting so called "zero-knowledge" protocols --- that are nevertheless hard to compute

#### Project

## Is the Casino using a Riffle Shuffle?

Our goal in this project is to understand how one can test if a particular dealer's shuffles follow a certain pattern. We have developed a theoretical framework for the same and wish to understand its performance in practice.

## Nick Gravin

#### Project

## Understanding neural networks in the brain

We aim to develop fully automated algorithms for mapping networks within biological brains.

#### Project

## Leader Election in the SINR Model with Arbitrary Power Control

We study the leader election problem in a theoretical wireless network setting. We show that it can be solved in two communication rounds.

## Magnus Halldorsson

## Stephan Holzer

#### Project

## Splinter: Practical Private Queries on Public Data

Splinter protects users’ queries on public data and scales to realistic applications.

#### Project

## Data Garbling: Computing on Encrypted Data

We are investigating the limits of computing on encrypted data, with a focus on the private outsourcing of computation over sensitive data.

#### Project

## Efficient Robust Estimation in High Dimensions

We are developing robust estimators for multivariate distributions which are both computationally efficient and near-optimal in terms of their accuracy. Our focus is on methods which are both theoretically sound and practically effective.

#### Project

## Covering All K-mers Using Joker Characters

We developed a new algorithm to generate compact sequence sets covering all k-mers using joker characters.

#### Project

## Matrix Permanents and Linear Optics

We use tools from quantum physics to prove new results in classical complexity.

#### Project

## Wikum: Bridging Discussion Systems and Wikis with Collective Summarization

We build tools to allow a community of people to collectively summarize large discussions online and manage knowledge embedded within these discussions.

#### Project

## Squadbox: Combating Online Harassment using Friendsourced Moderation

Fight back against online harassment with a squad of friends.

#### Project

## Multi-Core Data Structures

We aim to develop data structures optimized for large-scale multi-core computers.

#### Project

## Distributed Computation in Ant Colonies

We are interested in applying insights from distributed computing theory to understand how ants and other social insects work together to perform complex tasks such as foraging for food, allocating tasks to workers, and choosing high quality nest sites.

#### Project

## Towards Context-Aware Functional Genomics

We aim to develop a context-aware data-driven functional genomics framework that can characterize tissue-specific gene representations, provide context-aware genotype to phenotype mapping, and enable network-based exploration of disease genetics.

#### Project

## Reconstructing Neural Circuits from Mammalian Brain

We develop algorithms, systems and software architectures for automating reconstruction of accurate representations of neural tissue structures, such as nanometer-scale neurons' morphology and synaptic connections in the mammalian cortex.

#### Leads

#### Research Areas

#### Impact Areas

#### Project

## Performance Engineering of Cache Profilers

Our goal is to develop lightweight tools that allow programmers to better understand the cache performance of their applications. Tasks include designing profilers, performance engineering existing ones, and exploring different metrics for cache interactions.

#### Leads

#### Research Areas

#### Project

## Bellmania

Deductive synthesis for large-scale implementations of dynamic programming algorithms

#### Project

## Algorithmic Aspects of Performance Engineering

The project concerns algorithmic solutions for writing fast codes.

#### 24 More

## News

## Ryan Williams earns 2024 Gödel Prize

Ryan Williams, MIT EECS professor and CSAIL member, received the Gödel Prize for his “algorithms to lower bounds” paradigm.

## Scientists use generative AI to answer complex questions in physics

A new technique that can automatically classify phases of physical systems could help scientists investigate novel materials.

## CSAIL’s Rus and Indyk elected to the National Academy of Sciences

Two MIT professors who are affiliated with CSAIL have been elected to the prestigious NAS.

## Vaikuntanathan named a 2024 MacVicar Faculty Fellow

Professors Berggren, Campbell, Pollock, and Vaikuntanathan are honored for exceptional undergraduate teaching.

## Q&A: Global challenges surrounding the deployment of AI

Aleksander Madry, Asu Ozdaglar, and Luis Videgaray, co-chairs of the AI Policy Forum, discuss key issues facing the AI policy landscape today.

## Using AI to optimize for rapid neural imaging

MIT CSAIL researchers combine AI and electron microscopy to expedite detailed brain network mapping, aiming to enhance connectomics research and clinical pathology.

## NIH awards funding to BRAIN CONNECTS project involving CSAIL researchers

The NIH has awarded funding to a BRAIN CONNECTS project that includes efforts from CSAIL researchers, helping make connectomics tools more accessible and efficient to scale to a much larger neuroscience community.

## Two CSAILers named 2023 Simons Investigators

The program supports “outstanding theoretical scientists.”

## MIT engineers use kirigami to make ultrastrong, lightweight structures

Produced with techniques borrowed from Japanese paper-cutting, the strong metal lattices are lighter than cork and have customizable mechanical properties.

## Using AI to protect against AI image manipulation

“PhotoGuard,” developed by MIT CSAIL researchers, prevents unauthorized image manipulation, safeguarding authenticity in the era of advanced generative models.

## Educating national security leaders on artificial intelligence

Experts from MIT’s School of Engineering, Schwarzman College of Computing, and Sloan Executive Education educate national security leaders in AI fundamentals.

## Goldwasser awarded 2023 Dijkstra Prize in Distributed Computing

Shafi Goldwasser, MIT EECS, UC Berkeley, and Weizmann Institute of Science professor and CSAIL member, was recently awarded the 2023 Dijkstra Prize in Distributed Computing alongside a team of researchers for their work on “Completeness theorems for non-cryptographic fault-tolerant distributed computation.”

## New model offers a way to speed up drug discovery

By applying a language model to protein-drug interactions, researchers can quickly screen large libraries of potential drug compounds.

## Julia 1.9 available now

JuliaHub, MIT and WashU developers unveil major update to Julia programming language: a more nimble experience that may tilt the balance towards Julia for more users.

## Indyk elected to American Academy of Arts & Sciences

The American Academy of Arts & Sciences recently elected MIT EECS professor, CSAIL member, and co-director of Foundations of Data Science Institute (FODSI) Piotr Indyk as one of their members.

## Yael Tauman Kalai PhD ’06 awarded 2022 ACM Prize in Computing

The Association for Computing Machinery (ACM) recently awarded Yael Tauman Kalai, MIT Department of Electrical Engineering and Computer Science (EECS) adjunct professor, CSAIL member, and Senior Principal Researcher at Microsoft Research with the 2022 ACM Prize in Computing for her cryptography research.

## CSAIL's Rubinfeld named a 2023 Guggenheim Fellow

The John Simon Guggenheim Memorial Foundation recently awarded MIT EECS Professor and CSAIL principal investigator Ronitt Rubinfeld with a 2023 fellowship for her exceptional computer science research.

## CSAIL professor to Congress: “We are at an inflection point” with AI

Aleksander Mądry urges lawmakers to ask rigorous questions about how AI tools are being used by corporations.

## CSAIL's Daskalakis honored as 2022 ACM Fellow

MIT professor and CSAIL principal investigator Constantinos Daskalakis is one of six researchers with ties to MIT recognized by ACM for significant contributions to computing systems.

## MIT CSAIL community members win 2023 IEEE medals and awards

Seven faculty and alumni are among the winners of the prestigious honors for electrical engineers and computer scientists, including three CSAILers.

## A faster way to preserve privacy online

New research enables users to search for information without revealing their queries, based on a method that is 30 times faster than comparable prior techniques.

## Busy GPUs: Sampling and pipelining method speeds up deep learning on large graphs

New technique significantly reduces training and inference time on extensive datasets to keep pace with fast-moving data in finance, social networks, and fraud detection in cryptocurrency.

## CSAIL pioneer Tom Leighton awarded IEEE John von Neumann Medal

CSAILer Leighton won the IEEE Medal for his innovative work in designing algorithms.

## MIT CSAIL PhD students receive Best Student Paper at SuperComputing 2022

MIT CSAIL PhD students recently received the award as part of a team that includes Argonne National Lab and Technical University of Munich researchers.

## Shor awarded Breakthrough Prize in Fundamental Physics

MIT professor and CSAIL principal investigator Peter Shor recently received the 2023 Breakthrough Prize in Fundamental Physics for his pioneering work in the field of quantum information.

## Keeping web-browsing data safe from hackers

Studying a powerful type of cyberattack, researchers identified a flaw in how it’s been analyzed before, then developed new techniques that stop it in its tracks.

## The Millionth Algorithm: the runaway success of a foundational textbook

Introduction to Algorithms, which recently topped one million copies sold, is regarded as a fundamental textbook.

## Theoretical breakthrough could boost data storage

New work on linear-probing hash tables from MIT CSAIL could lead to more efficient data storage and retrieval in computers.

## Automating the search for entirely new “curiosity” algorithms

Researchers show that computers can “write” algorithms that adapt to radically different environments better than algorithms designed by humans.

## “Doing machine learning the right way”

Professor Aleksander Madry strives to build machine-learning models that are more reliable, understandable, and robust.

## Finding the true potential of algorithms

Using mathematical theory, Virginia Williams coaxes algorithms to run faster or proves they’ve hit their maximum speed.

## CSAIL's Daskalakis wins ACM Grace Murray Hopper Award

Constantinos (“Costis”) Daskalakis, an MIT professor and CSAIL principal investigator, has won the 2018 ACM Grace Murray Hopper Award.

## CSAIL’s Tom Leighton receives Marconi Prize, top prize in communications technology

CSAIL’s Tom Leighton receives Marconi Prize, top prize in communications technology

## Goldwasser, Micali, and Rivest win BBVA Foundation Frontiers of Knowledge Awards

This week it was announced that MIT professors and CSAIL principal investigators Shafi Goldwasser, Silvio Micali, Ronald Rivest, and former MIT professor Adi Shamir won this year’s BBVA Foundation Frontiers of Knowledge Awards in the Information and Communication Technologies category for their work in cryptography.

## Goldwasser gives briefing on cryptography to Congress

Last week CSAIL principal investigator Shafi Goldwasser spoke about cryptography and privacy as part of the annual congressional briefing of the American Mathematical Society (AMS) and the Mathematical Sciences Research Institute (MSRI).