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

该项目解决了两个突出的算法问题的更快解决方案：矩阵乘法和广义离散傅立叶变换(DFT)。在这两种情况下，挑战都是获得快速算法。矩阵乘法是理论计算机科学中的一个中心问题，这既是因为它内在的数学吸引力，也是因为这个基本问题的改进算法将立即导致对各种相关问题的改进算法。广义DFT也是类似的基本原理，涉及以某些在数学上有意义的方式转换数据。这两个问题的最佳快速算法一直是悬而未决的问题。这样的算法将在计算机科学内外产生后果和应用。该项目的明确目标是增加计算机科学和数学之间卓有成效的互动，并将研究计划的适当方面整合到各级学生的教学和培训中。该项目的目标是为这两个问题实现“近线性”时间算法，在DFT的情况下，实现关于所有有限群的近线性时间算法。这两个问题都有丰富的结构，很容易被复杂的数学处理。DFT本质上涉及群论和表示论，而该项目的矩阵乘法方法利用这些发展良好的数学领域来获得快速的矩阵乘法算法。一个主要的技术目标是开发和利用最近在组合学方面的突破(“上限集猜想”的解决方案)，作为努力寻找或构建合适的组族的工具，这些组族可以产生所需的矩阵乘法的近线性时间算法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.