Award Abstract # 1423544
AF: Small: Algorithms for Matrix Multiplication, Polynomial Factorization and Generalized Fourier Transform

NSF Org: CCF
Division of Computing and Communication Foundations
Recipient: CALIFORNIA INSTITUTE OF TECHNOLOGY
Initial Amendment Date: June 13, 2014
Latest Amendment Date: June 13, 2014
Award Number: 1423544
Award Instrument: Standard Grant
Program Manager: Tracy Kimbrel
CCF
 Division of Computing and Communication Foundations
CSE
 Directorate for Computer and Information Science and Engineering
Start Date: July 1, 2014
End Date: June 30, 2017 (Estimated)
Total Intended Award Amount: $500,000.00
Total Awarded Amount to Date: $500,000.00
Funds Obligated to Date: FY 2014 = $500,000.00
History of Investigator:
  • Christopher Umans (Principal Investigator)
    umans@cs.caltech.edu
Recipient Sponsored Research Office: California Institute of Technology
1200 E CALIFORNIA BLVD
PASADENA
CA  US  91125-0001
(626)395-6219
Sponsor Congressional District: 28
Primary Place of Performance: California Institute of Technology
CA  US  91125-0001
Primary Place of Performance
Congressional District:
28
Unique Entity Identifier (UEI): U2JMKHNS5TG4
Parent UEI:
NSF Program(s): Algorithmic Foundations
Primary Program Source: 01001415DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 7923, 7926
Program Element Code(s): 779600
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.070

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.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

C. Hsu and C. Umans "A fast generalized DFT for finite groups of Lie type" Proceedings of SODA , 2018 https://arxiv.org/abs/1707.00349
C. Hsu and C. Umans "On multidimensional and monotone k-sum" Proceedings of MFCS. , 2017 http://users.cms.caltech.edu/~umans/papers/HU17a
J. Blasiak, T. Church, H. Cohn, J. Grochow, E. Naslund, W. Sawin, C. Umans "On cap sets and the group-theoretic approach to matrix multiplication" Discrete Analysis , v.3 , 2017 http://discreteanalysisjournal.com/article/1245-on-cap-sets-and-the-group-theoretic-approach-to-matrix-multiplication
W. Hoza and C. Umans "Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace" Proceedings of the 49th Annual Symposium on Theory of Computing (STOC) , 2017 , p.629 https://arxiv.org/abs/1610.01199
Zeyu Guo, Anand Narayanan and Chris Umans "Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields." Proceedings of MFCS , 2016 abs/1606.04592
Zeyu Guo and He Sun "Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading" SODA , 2015 , p.411 10.1137/1.9781611973730.29

PROJECT OUTCOMES REPORT

Disclaimer

This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.

This project concerned three prominent problems in algorithms. The first is an effort to obtain fast algorithms for multiplying matrices, using a general approach known as the "group-theoretic" approach. The second is an effort to obtain fast algorithms for factoring polynomials into their irreducible components. The third is an effort to obtain fast algorithms for performing a fundemental algebraic transformation called the "generalized Discrete Fourier Transform (DFT)" with respect to any finite group. In each case the goal is to devise algorithms that use a number of computational steps roughly proportional to the size of the input. 

During the course of this project, the PI made significant progress on all three problems. In the case of matrix multiplication, the major outcome is the development of a robust technique for ruling out certain groups as potential means for implementing the group-theoretic approach. This disproves an earlier popular conjecture arising as part of the group-theoretic approach, and rules out large classes of groups, while giving new information about which groups are suitable targets. The results and techniques generalize the recent breakthrough proof of the so-called "cap-set conjecture" from combinatorics, and are of independent interest. 

In the case of factoring polynomials, the main result is an explanation for the difficulty of breaking the "exponent 3/2" barrier in algorithms for this problem, in the form of reductions between an assortment of algebraic problems so that improving exponent 3/2 for any one of them would improve it for all of them.

For the generalized DFT, the main result is an algorithm with the targeted (optimal) running time for a broad class of groups known as linear groups, which contains groups that had been regarded as the most difficult open cases. The new algorithm relies on a novel divide and conquer approach that will likely play an role in the complete resolution of the problem. The best generic algorithm for generalized DFTs with respect to any group, now has exponent 1.414... (under an assumption about the complexity of matrix multiplication)  which improves the previous best, 1.5, the first improvement in more than 30 years.

During the course of this project, the PI mentored one graduate student and two postdocs who worked on the supported research topics, and worked closely with a number of undergraduate students on research projects. All of these undergraduate students went on to top Ph.D. programs, and several won national-level awards. Research content concerning matrix multiplication was integrated into advanced course offerings, and the PI gave a number of invited lectures on this topic and others, including high-profile lectures aimed at the general scientifically-interested public.  


Last Modified: 02/18/2018
Modified by: Christopher M Umans

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page