AF: Small: Algebraic Tools for Coding, Complexity and Combinatorics

该项目开发代数工具，应用于计算复杂性、编码理论和关联几何。这些应用领域描述了计算机科学、电气和数学领域中的三个领域，这些领域受到非常不同的动机的驱动。计算复杂性旨在了解算法的基本限制。编码理论旨在研究能够保护数字信息免受不可避免地潜入每个存储介质或通信渠道的错误的方法。关联几何研究空间中满足良好几何性质的点的组合性质，如维度大小。尽管在范围上有很大的不同，但这三个领域的许多核心结果都是通过对函数的基本代数性质的理解而得出的。该项目旨在进一步发展这一基本理解，以使更多的此类应用程序能够实现，并将这些领域结合在一起。这个项目中正在探索的一些核心代数性质包括：(1)检验多元函数本质上是否为低次多项式的高效随机化方法；(2)研究代数性质的对称性如何实现高效检验；以及(3)在关联几何研究中使用高阶导数。该项目涉及对初级研究人员(博士候选人)的指导和教育，他们打算在研究领域追求自己的职业生涯，特别是那些对数学、电气工程和计算机科学领域的跨学科研究感兴趣的人。该项目的教育部分将开发这一跨学科研究项目中使用的课程和材料，从而也有助于促进其广泛影响。

This project develops algebraic tools for applications in computational complexity, coding theory and incidence geometry. These application domains describe three areas within the fields of computer science, electrical and mathematics driven by very distinct motivations. Computational complexity aims to understand the fundamental limits of algorithms. Coding theory aims to study methods that can protect digital information from errors that inevitably creep in to every storage medium or communication channel. Incidence geometry studies combinatorial properties, such as size of dimension, of points in space that satisfy nice geometric properties. Despite the vast difference in scope, many central results in the three areas have come about by an understanding of basic algebraic properties of functions. This project aims to develop this basic understanding further to enable many more of such applications, and to bring these areas together. Some central algebraic properties that are being explored in this project include (1) highly-efficient randomized methods to test if a multivariate function is essentially a low-degree polynomial, (2) study of how symmetries of algebraic properties enable highly-efficient tests, and (3) use of higher-order derivatives in the study of incidence geometry. The project involves the mentoring and education of junior researchers (Ph.D. candidates) who intend to pursue their own careers in research, especially those interested in interdisciplinary studies within mathematics, electrical engineering and computer science. The education component of this project will develop courses and material of use in this interdisciplinary research project, and thus also help contribute to its broad impact.