AF: Small: Group Theory and Representation Theory in Matrix Multiplication and Generalized DFTs

California Institute Of Technology, Pasadena CA

Investigators

Abstract

This project addresses faster solutions to two prominent algorithmic problems: matrix multiplication and the generalized Discrete Fourier Transform (DFT). In both cases, the challenge is to obtain fast algorithms. Matrix multiplication is a central problem in theoretical computer science, both because of its intrinsic mathematical appeal, and because improved algorithms for this fundamental problem would lead immediately to improved algorithms for a broad variety of related problems. The generalized DFT is similarly fundamental, and concerns transforming data in certain mathematically meaningful ways. Optimally fast algorithms for both problems have been longstanding open questions. Such algorithms would have consequences and applications both within and beyond computer science. The project explicitly aims to increase fruitful interactions between computer science and mathematics, and to integrate appropriate aspects of the research program into teaching and training of students at all levels. The project's goal is to achieve "nearly-linear" time algorithms for both problems, and in the case of the DFT, nearly-linear time algorithms with respect to all finite groups. Both problems possess rich structure that is susceptible to a sophisticated mathematical treatment. The DFT inherently involves group theory and representation theory, while the project's approach to matrix multiplication employs these well-developed areas of mathematics to obtain fast matrix multiplication algorithms. A major technical goal is to develop and leverage a recent breakthrough in combinatorics (the resolution of the "Cap Set Conjecture") as a tool in the effort the find or construct a suitable family of groups that can yield the desired nearly-linear time algorithm for matrix multiplication. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.