CAREER: Algebraic and Geometric Complexity Theory

职业：代数和几何复杂性理论

• 批准号: 2047310
• 负责人: Michael Forbes
• 金额: $ 50万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-03-01 至 2026-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2047310&HistoricalAwards=false
• 关键词: CAREER; Algebraic; Geometric; Complexity; Theory

Understanding the limits of efficient computation is central to the theory of computer science. These limits dictate what can be expected from the algorithms that are coded, and justify beliefs in the security of cryptography. The use of algebraic techniques (multiplication, derivatives, and beyond) is pervasive in the design of efficient computation. These techniques apply to problems inherently of an algebraic nature, as well for tasks that seemingly lack algebraic structure. This project seeks to understand the power of these techniques through two different lenses. The first aims to show how to efficiently eliminate the use of randomness in algebraic algorithms. The second aims to leverage the deep mathematical structure of algebraic algorithms to define limits on their computational power. These two aims are connected through attention to common techniques and models of algebraic computation. The project will promote study of algebraic computation in general through course design, organization of workshops, and training of undergraduate and graduate students.In particular, this project seeks to design deterministic algorithms for deciding whether a given algebraic expression simplifies to a trivial expression, a problem known as polynomial identity testing (PIT). While efficient randomized algorithms for PIT have been known for decades, developing deterministic algorithms has proven challenging. The project identifies classes of PIT problems which are both of fundamental importance and that are ripe for further progress. Deterministically solving these PIT problems would settle key challenges in the area, and also lead to new algorithms in areas outside algebraic computation. Developing such deterministic PIT algorithms is known in general to be equivalent to establishing limits on efficient algebraic computation, and as such this project seeks to establish such limits through the geometric complexity theory (GCT) program. This program has seen significant overall interest from the research community, but has seen fewer than desired results due to the high barriers to entry arising from steep mathematical prerequisites. The project offers a set of problems within this program that both are of fundamental importance, but also are concretely solvable. The selection of these problems is informed by corresponding progress made in developing deterministic PIT algorithms, and as such the two parts of the project will develop in tandem.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.

理解有效计算的极限是计算机科学理论的核心。 这些限制决定了可以从编码的算法中期望什么，并证明了密码学安全性的信念。 代数技术（乘法、导数等）的使用在高效计算的设计中很普遍。 这些技术适用于本质上具有代数性质的问题，以及似乎缺乏代数结构的任务。 这个项目试图通过两个不同的镜头来理解这些技术的力量。 第一个目的是展示如何有效地消除代数算法中的随机性。 第二个目标是利用代数算法的深层数学结构来定义其计算能力的限制。 这两个目标是通过关注代数计算的常见技术和模型连接起来的。 本项目将通过课程设计、研讨会的组织、本科生和研究生的培养等，促进代数计算的一般性研究。特别是，本项目旨在设计确定性算法，以确定给定的代数表达式是否简化为平凡表达式，这一问题被称为多项式恒等式测试（PIT）。 虽然用于PIT的有效随机算法已经存在了几十年，但开发确定性算法已被证明具有挑战性。 该项目确定类的PIT问题，这是根本的重要性，是成熟的进一步的进展。 确定性地解决这些PIT问题将解决该领域的关键挑战，并在代数计算之外的领域产生新的算法。 开发这种确定性PIT算法通常被认为等同于建立有效代数计算的限制，因此本项目试图通过几何复杂性理论（GCT）程序建立这种限制。 该计划已经看到了显着的整体兴趣，从研究界，但已经看到了低于预期的结果，由于高门槛进入所产生的陡峭的数学先决条件。 该项目提供了一系列问题，在这个程序中，这两个都是根本的重要性，但也是具体的解决方案。 这些问题的选择是根据确定性PIT算法开发的相应进展而确定的，因此项目的两个部分将同步发展。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

项目成果

Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals

• DOI: 10.1145/3519935.3520025
• 发表时间: 2021-12
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Robert Andrews;Michael A. Forbes

On Matrix Multiplication and Polynomial Identity Testing

关于矩阵乘法和多项式恒等性检验

• DOI: 10.1109/focs54457.2022.00041
• 发表时间: 2022
• 期刊: FOCS 2022
• 作者: Andrews, Robert