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算法通常是相当于建立有效的代数计算的限制，因此该项目试图通过几何复杂性理论（GCT）计划来建立此类限制。 该计划引起了研究界的总体兴趣，但由于陡峭的数学先决条件引起的进入障碍的高障碍，结果少于预期的结果。 该项目在该计划中提供了一组问题，两者都至关重要，但也可以解决。 这些问题的选择是通过在开发确定性坑算法中取得的相应进展来告知的，因此该项目的两个部分将在同时发展。该奖项反映了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