CAREER: Algebraic and Geometric Complexity Theory

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

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.