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

AF：小：用于编码、复杂性和组合学的代数工具

• 批准号: 1420956
• 负责人: Madhu Sudan
• 金额: $ 50万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2015-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1420956&HistoricalAwards=false
• 关键词: AF; Small; Algebraic; Tools; Coding

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.

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