AF: Small: Algorithms for Matrix Multiplication, Polynomial Factorization and Generalized Fourier Transform

California Institute Of Technology, Pasadena CA

Investigators

Abstract

This project addresses three prominent algorithmic problems: matrix multiplication, polynomial factorization, and the generalized discrete Fourier transform (DFT). In the first two, the challenge is to obtain fast algorithms for basic manipulations of matrices and polynomials, and in the third, the challenge is to obtain fast algorithms for transforming data in certain mathematically meaningful ways. Matrix multiplication is a central open problem in theoretical computer science, both because of its intrinsic mathematical appeal, and because improved algorithms for this important problem would have immediate consequences for a broad variety of related problems. Univariate polynomial factorization occupies a similar central position among the basic operations on polynomials, and the generalized DFT is one of the most interesting and useful linear maps, with structure that should admit a fast algorithm. All three problems are fundamental and longstanding open problems, and they have a diversity of applications in computer science, and beyond. The project's goal is to achieve "nearly-linear" time algorithms for all three problems. These problems possess rich structure that is susceptible to a sophisticated mathematical treatment; for example, one technique is to embed matrix multiplication into algebraic structures arising from groups and coherent configurations. This project develops these ideas, and at the same time aims to make further progress by injecting some more "computer science"-style ideas -- recursion, approximation, reductions, relaxations, and a mixture of Boolean computation with algebraic operations. Because all three focus areas of this project revolve around difficult and longstanding open problems, the project will take concrete steps towards (1) building up understanding and (2) developing useful machinery, both aimed at an eventual resolution of these central algorithmic problems.