AF: Small: Algorithms for Matrix Multiplication, Polynomial Factorization and Generalized Fourier Transform
AF:小:矩阵乘法、多项式分解和广义傅立叶变换算法
基本信息
- 批准号:1423544
- 负责人:
- 金额:$ 50万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2014
- 资助国家:美国
- 起止时间:2014-07-01 至 2017-06-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
This project addresses three prominent algorithmic problems: matrix multiplication, polynomial factorization, and the generalized discrete Fourier transform (DFT). In the first two, the challenge is to obtain fast algorithms for basic manipulations of matrices and polynomials, and in the third, the challenge is to obtain fast algorithms for transforming data in certain mathematically meaningful ways. Matrix multiplication is a central open problem in theoretical computer science, both because of its intrinsic mathematical appeal, and because improved algorithms for this important problem would have immediate consequences for a broad variety of related problems. Univariate polynomial factorization occupies a similar central position among the basic operations on polynomials, and the generalized DFT is one of the most interesting and useful linear maps, with structure that should admit a fast algorithm. All three problems are fundamental and longstanding open problems, and they have a diversity of applications in computer science, and beyond.The project's goal is to achieve "nearly-linear" time algorithms for all three problems. These problems possess rich structure that is susceptible to a sophisticated mathematical treatment; for example, one technique is to embed matrix multiplication into algebraic structures arising from groups and coherent configurations. This project develops these ideas, and at the same time aims to make further progress by injecting some more "computer science"-style ideas -- recursion, approximation, reductions, relaxations, and a mixture of Boolean computation with algebraic operations. Because all three focus areas of this project revolve around difficult and longstanding open problems, the project will take concrete steps towards (1) building up understanding and (2) developing useful machinery, both aimed at an eventual resolution of these central algorithmic problems.
该项目解决了三种突出的算法问题:矩阵乘法,多项式分解和广义的离散傅立叶变换(DFT)。在前两个中,挑战是获得对矩阵和多项式基本操作的快速算法,而在第三个挑战中,挑战是获得快速算法,以以某些数学上有意义的方式转换数据。矩阵乘法是理论计算机科学中的一个核心开放问题,这既是由于其内在的数学吸引力,又是因为改善了这个重要问题的算法将对各种相关问题产生直接的后果。单变量多项式分解在多项式上的基本操作中占据了类似的中心位置,并且广义DFT是最有趣,最有用的线性图之一,结构应接收快速算法。这三个问题都是基本的和长期存在的开放问题,它们在计算机科学及其他方面都有多种应用。该项目的目标是实现所有三个问题的“接近线性”时间算法。这些问题具有丰富的结构,容易受到复杂的数学处理。例如,一种技术是将矩阵乘法嵌入由组和相干配置引起的代数结构中。该项目开发了这些想法,同时旨在通过注入更多“计算机科学”式的想法 - 递归,近似,减少,放松以及布尔计算与代数操作的混合在一起。由于该项目的所有三个重点领域都围绕着困难且长期存在的开放问题,因此该项目将采取具体的步骤(1)建立理解和(2)开发有用的机械,均旨在最终解决这些中心算法问题。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Christopher Umans其他文献
Pseudorandomness for Approximate Counting and Sampling
近似计数和采样的伪随机性
- DOI:
- 发表时间:
2006 - 期刊:
- 影响因子:0
- 作者:
Ronen Shaltiel;Christopher Umans - 通讯作者:
Christopher Umans
Christopher Umans的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Christopher Umans', 18)}}的其他基金
AF: Small: Group Theory and Representation Theory in Matrix Multiplication and Generalized DFTs
AF:小:矩阵乘法和广义 DFT 中的群论和表示论
- 批准号:
1815607 - 财政年份:2018
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Algebraic Methods for Core Problems in Algorithms and Complexity
AF:小:算法和复杂性核心问题的代数方法
- 批准号:
1116111 - 财政年份:2011
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
New Applications of Error-Correcting Codes in Complexity and Algorithms
纠错码在复杂性和算法方面的新应用
- 批准号:
0830787 - 财政年份:2008
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
CAREER: Research in Complexity Theory with Applications
职业:复杂性理论及其应用研究
- 批准号:
0346991 - 财政年份:2004
- 资助金额:
$ 50万 - 项目类别:
Continuing Grant
相似国自然基金
员工算法规避行为的内涵结构、量表开发及多层次影响机制:基于大(小)数据研究方法整合视角
- 批准号:72372021
- 批准年份:2023
- 资助金额:40 万元
- 项目类别:面上项目
基于球面约束和小波框架正则化的磁共振图像处理变分模型与快速算法
- 批准号:12301545
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
基于谱图小波变换算法的2型糖尿病肠道微生物组学网络标志物筛选研究
- 批准号:
- 批准年份:2022
- 资助金额:30 万元
- 项目类别:青年科学基金项目
用于非小细胞肺癌免疫疗效预测的复合传感模式电子鼻构建及智能算法研究
- 批准号:
- 批准年份:2021
- 资助金额:57 万元
- 项目类别:面上项目
基于相关关系信息增强的遥感图像小目标快速检测算法研究
- 批准号:
- 批准年份:2021
- 资助金额:30 万元
- 项目类别:青年科学基金项目
相似海外基金
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF:RI:Small: Fairness in allocation and machine learning problems: algorithms and solution concepts
AF:RI:Small:分配公平性和机器学习问题:算法和解决方案概念
- 批准号:
2334461 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
AF: Small: Communication-Aware Algorithms for Dynamic Allocation of Heterogeneous Resources
AF:小型:用于异构资源动态分配的通信感知算法
- 批准号:
2335187 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347321 - 财政年份:2024
- 资助金额:
$ 50万 - 项目类别:
Standard Grant