AF: Small: Algebraic Methods for Core Problems in Algorithms and Complexity

这个项目的目标是算法和复杂性中的一些具有挑战性的问题，这些问题可以用代数方法解决。研究围绕三个主要目标组织：1。以实现近线性运行时间为目标的矩阵乘法算法（即，证明矩阵乘法指数等于2）。以实现近线性运行时间为目标的多项式分解算法；以对数种子长度和最优输出长度为目标的随机提取器的显式构造。该项目的第二个目标是明确培养具有更广泛适用性的新颖代数方法，并在选择问题和方法时考虑到这一点。矩阵乘法是理论计算机科学中的一个核心开放问题，对于这个重要问题的改进算法将对一系列广泛的相关问题产生直接影响。单变量多项式分解是对多项式的类似的基本操作，并且它是目前尚不知道近线性时间算法的极少数此类问题之一。随机提取器是具有随机特性的不平衡二部图，它已经成为理论计算机科学（以及其他领域）的一个基本对象，具有跨越复杂性、算法、分布式系统、密码学、编码理论、压缩感知和其他领域的大量应用。解决基本的开放问题，如本项目所针对的问题，增强了我们对高效计算的理解和掌握。

This project targets a number of challenging problems in Algorithms and Complexity that are amenable to an algebraic approach. Research is organized around three major goals: 1. Algorithms for matrix multiplication with the aim of achieving nearly-linear running time (i.e., proving that the matrix multiplication exponent equals 2).2. Algorithms for polynomial factorization with the aim of achieving nearly-linear running time, and 3. Explicit constructions of randomness extractors with the aim of achieving logarithmic seed length and optimal output length. A secondary aim of this project is to explicitly cultivate novel algebraic methods with broader applicability, and the choice of problems and approaches is made with this in mind. Matrix multiplication is a central open problem in theoretical computer science, and improved algorithms for this important problem would have immediate consequences for a broad array of related problems. Univariate polynomial factorization is a similarly fundamental operation on polynomials, and it stands out as one of a very few such problems for which nearly-linear time algorithms are not yet known. Randomness extractors are unbalanced bipartite graphs with random-like properties that have emerged as a fundamental object in theoretical computer science (and beyond) with a huge array of applications spanning Complexity, Algorithms, Distributed Systems, Cryptography, Coding Theory, Compressed Sensing, and other areas. Resolving fundamental open problems such as those targeted in this project enhances our understanding and mastery of efficient computation.