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.