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.
We work on improving the algorithms for algebraic problems like matrix multiplication, and using these to design algorithms for fundamental non-algebraic problems.
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.
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.
Our interests span quantum complexity theory, barriers to solving P versus NP, theoretical computer science with a focus on probabilistically checkable proofs (PCP), pseudo-randomness, coding theory, and algorithms.
Theory research at CSAIL covers a broad spectrum of topics, including algorithms, complexity theory, cryptography, distributed systems, parallel computing and quantum computing.
