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

AF：小：算法和复杂性核心问题的代数方法

• 批准号: 1116111
• 负责人: Christopher Umans
• 金额: $ 35万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1116111&HistoricalAwards=false
• 关键词: AF; Small; Algebraic; Methods; Core

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.

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