Theory research at CSAIL covers a broad spectrum of topics, including algorithms, complexity theory, cryptography, distributed systems, parallel computing and quantum computing.

#### Research Group

# Theory of Computation Group

Theory research at CSAIL covers a broad spectrum of topics, including algorithms, complexity theory, cryptography, distributed systems, parallel computing and quantum computing.

Last updated Mar 20 '18

We look at classical problems with the aesthetics of computational complexity and ask questions concerning non-determinism, randomness, approximation, interaction, and locality. We’ve also played a foundational role in addressing challenges arising in computer systems and networks, such as error-free communication, cryptography, routing, and search. We are also now a rising force in the sciences: exact, life, and social.

#### Research Areas

#### Impact Areas

## Members

## Projects

#### Project

## Eyebrowse: Social and Public Web Browsing

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

#### 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

## 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

## Understanding GANs

Generative adversarial networks (GANs) are a powerful but poorly understood tool for unsupervised learning. We seek to build a principled understanding of why they work, and why they can sometimes fail.

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

#### Project

## Understanding neural networks in the brain

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

#### Project

## Splinter: Practical Private Queries on Public Data

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

#### Project

## Algorithmic Aspects of Performance Engineering

The project concerns algorithmic solutions for writing fast codes.

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

## Lea Verou

#### 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

#### 25 More

## News

## 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).