
NSF Org: |
CCF Division of Computing and Communication Foundations |
Recipient: |
|
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: |
|
History of Investigator: |
|
Recipient Sponsored Research Office: |
1200 E CALIFORNIA BLVD PASADENA CA US 91125-0001 (626)395-6219 |
Sponsor Congressional District: |
|
Primary Place of Performance: |
CA US 91125-0001 |
Primary Place of
Performance Congressional District: |
|
Unique Entity Identifier (UEI): |
|
Parent UEI: |
|
NSF Program(s): | Algorithmic Foundations |
Primary Program Source: |
|
Program Reference Code(s): |
|
Program Element Code(s): |
|
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.
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.