Josh Alman

Much of his work focuses on how quickly one can perform basic algebraic tasks, and how computational algebraic tools can be applied to problems throughout computer science.

Alman combines insights from both algorithm design and complexity theory to approach problems in his research. Two topics he has studied extensively are algorithms for matrix multiplication, and algorithms for computing important linear transforms such as Fourier transforms.

His work on matrix multiplication gives the fastest known algorithm for multiplying two matrices, and also proves mathematical barrier results explaining why computer scientists have been unable to design even faster algorithms for this important problem.

His work on linear transforms focuses on a technique called matrix rigidity, which studies how well the matrices underlying computational tasks can be decomposed as a sum of a low-rank matrix and a sparse matrix. He has shown that important transforms like the Walsh-Hadamard transform have more efficient decompositions than previously conjectured to be possible, and he has given the first non-trivial construction of matrices without an efficient decomposition.

He has employed these and other techniques from algorithms, complexity, and algebra to a diverse set of problems throughout computer science, including nearest neighbor search, streaming algorithms, dynamic graph algorithms, fine-grained complexity, communication complexity, and data structure lower bounds.

Alman earned a BS in mathematics from MIT in 2014, an MS in computer science from Stanford in 2016, and a PhD in computer science from MIT in 2019. Before coming to Columbia, he was a Michael O. Rabin postdoctoral fellow in theoretical computer science at Harvard University.

Research Areas

• Applied and Theoretical Machine Learning
• Algorithms & Complexity Theory