CAREER: Algebraic and Geometric Complexity Theory

理解高效计算的极限是计算机科学理论的核心。这些限制规定了可以从编码的算法中期待什么，并证明了对密码学安全性的信念。代数技术(乘法、导数等)的使用在高效计算的设计中非常普遍。这些技巧适用于本质上具有代数性质的问题，也适用于似乎缺乏代数结构的任务。这个项目试图通过两个不同的镜头来理解这些技术的力量。第一个目的是展示如何有效地消除代数算法中随机性的使用。第二个目标是利用代数算法的深层数学结构来定义其计算能力的限制。这两个目标是通过关注常见的代数计算技术和模型而联系在一起的。该项目将通过课程设计、研讨会的组织以及本科生和研究生的培训来促进代数计算的学习。特别是，该项目寻求设计确定性算法来确定给定的代数表达式是否简化为平凡的表达式，这一问题被称为多项式恒等式测试(PIT)。虽然有效的PIT随机化算法几十年来一直是已知的，但开发确定性算法已被证明具有挑战性。该项目确定了几类既具有根本重要性又已成熟可供进一步发展的核不扩散问题。确定性地解决这些坑问题将解决该领域的关键挑战，也将导致代数计算以外的领域的新算法。众所周知，开发这种确定性的PIT算法通常等同于对有效的代数计算建立限制，因此，本项目试图通过几何复杂性理论(GCT)程序来建立这样的限制。这个项目总体上受到了研究界的极大关注，但由于严格的数学前提条件所产生的高门槛，结果比预期的要少。该项目提供了该项目中的一系列问题，这些问题既具有根本性的重要性，也是可以具体解决的。选择这些问题是因为在开发确定性PIT算法方面取得了相应的进展，因此该项目的两个部分将同时发展。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.