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

AF：小：矩阵乘法和广义 DFT 中的群论和表示论

基本信息

批准号：
1815607
负责人：
Christopher Umans
金额：
$ 50万
依托单位：
California Institute of Technology
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-06-01 至 2022-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1815607&HistoricalAwards=false
关键词：
AF Small Group Theory Representation

项目摘要

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.

该项目解决了两个突出算法问题的更快解决方案：矩阵乘法和广义离散傅立叶变换（DFT）。在这两种情况下，挑战是获得快速算法。矩阵乘法是理论计算机科学中的一个核心问题，这既是由于其内在的数学吸引力，又是因为改善了此基本问题的算法将立即导致针对各种相关问题的算法改善算法。广义DFT同样是基本的，并且涉及以某些数学有意义的方式转换数据。这两个问题的最佳快速算法都是长期以来的开放问题。这种算法在计算机科学内外都会产生后果和应用。该项目明确旨在提高计算机科学与数学之间的富有成果的互动，并将研究计划的适当方面整合到各个级别的学生的教学和培训中。该项目的目标是实现这两个问题的“几乎是线性”的时间算法，在DFT中，与DFT相对于所有有限的小组而言，DFT几乎是在DFT的情况下。这两个问题都具有丰富的结构，容易受到复杂的数学处理。 DFT固有地涉及群体理论和表示理论，而项目的矩阵乘法方法采用这些发达的数学领域来获得快速矩阵乘法算法。一个主要的技术目标是发展和利用组合学的最新突破（“ CAP SET猜想”的分辨率）作为努力的工具，以寻找或构建一个合适的团体家族，可以产生所需的几乎线性时间算法，用于矩阵乘法的临时奖励，这反映了NSF的法定任务和审查的范围。