Computer Science Thesis Proposal

Monday, May 2, 2022 - 3:00pm


In Person Gates Hillman 8102


KEVIN PRATT, Ph.D. Student Computer Science Department Carnegie Mellon University

High-Dimensional Expanders and Fast Matrix Multiplication

This proposal is based on recent progress on two topics: algorithms for fast matrix multiplication, and constructions of high- dimensional expanders (HDXs). Our approach to these topics is group- theoretic in nature.
The exponent of matrix multiplication, ω, governs the runtime of many basic linear-algebraic and combinatorial algorithms. In 2003, Henry Cohn and Chris Umans proposed a group-theoretic framework that captures the best-known upper bounds on ω. In joint work with Henry Cohn, Jonah Blasiak, Josh Grochow, and Chris Umans, we showed that groups of Lie type cannot yield ω = 2 within this framework. This is an important family of groups for which no barriers were previously known. Our proof builds on Gowers’ result concerning product-free sets in quasirandom groups. We also introduced a (continuous) Lie group analog of the exponent of matrix multiplication, which may be easier to understand.
High-dimensional expansion generalizes expansion in graphs to higher-dimensional simplicial complexes, and has motivated recent breakthroughs in classical and quantum coding theory and the analysis of Markov chains. Whereas almost all graphs have excellent expansion, there is a scarcity of (bounded degree, spectral) HDXs. In joint work with Ryan O’Donnell, we constructed several new families of HDXs: for each (untwisted) group of Lie type (except for G_2(q)), we gave a HDX whose top-dimensional faces are acted on simply-transitively by the group.
Thesis Committee:
Ryan O’Donnell (Chair)
Pravesh Kothari
Prasad Tetali
Alex Lubotzky (Weizmann Institute of Science))
Chris Umans (California Institute of Technology)

For More Information, Contact:


Thesis Proposal