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.