AF: Small: Algebraic Methods in Codes and Computation

这个项目调查了代数计算和代数技术在计算机科学中的力量和局限性。算术电路是一种非常自然的代数计算模型，大多数自然的代数算法，如矩阵乘法、快速傅立叶变换、行列式计算算法等都可以通过算术电路实现。这个项目将通过算术电路的模型来研究代数计算的复杂性。近年来，代数技术已经显示为一个极其强大的工具，影响着计算机科学的所有领域，甚至包括对本质上不是代数的问题的理解。代数技术在组合学、编码理论和伪随机性方面也有显著的应用。由于代数技术和代数算法的深刻影响，这自然促使人们对这些方法的能力和局限性有更深的理解，本项目旨在开发新的工具和技术来实现这一点。该项目的重点之一将是利用代数技术来构造高效和局部纠错码。对年轻研究人员的指导和培训是该项目教育组成部分的重要组成部分。此外，研究人员将在2020年夏天共同组织女性理论研讨会，该研讨会将汇集来自世界各地的理论计算机科学领域的女性研究人员。该项目将探索的两个主要问题是证明算术电路的下界和多项式恒等式测试问题。这些是代数复杂性理论中一些最核心的问题，本项目旨在通过对有界深度算术电路的研究来理解这些问题。该项目还将研究另外两个非常相关的问题，即多项式因式分解和多项式重构。此外，该项目将使用代数技术来构造新的纠错码族，这些纠错码具有极其有效的编码和次线性时间解码和测试算法。特别是，该项目将试图了解在构建本地可解码代码和本地可测试代码时的最佳速率/查询复杂性权衡。这个项目将汇集来自广泛学科的想法和工具，并有可能在信息存储和检索方面有重要的实际应用。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This project investigates the power and limitations of algebraic computation and algebraic techniques in computer science. Arithmetic circuits are a very natural model of algebraic computation and most natural algebraic algorithms such as matrix multiplication, fast Fourier transforms, algorithms for computing the determinant, and others can be implemented via arithmetic circuits. This project will investigate the complexity of algebraic computation via the model of arithmetic circuits. In recent years algebraic techniques have shown up as an extremely powerful tool influencing all areas of computer science, including even the understanding of problems that are not inherently algebraic. Algebraic techniques have also found striking applications in combinatorics, coding theory, and pseudorandomness. Due to the profound impact of algebraic techniques and algebraic algorithms, this naturally motivates a deeper understanding of the power and limits of these methods, and this project aims to develop new tools and techniques in order to do this. One of the focuses of the project will be to harness algebraic techniques for the construction of efficient and local error-correcting codes. Mentoring and training of young researchers is an important part of the educational component of the project. Additionally, the investigator will co-organize the Women in Theory workshop in the summer of 2020, which will bring together women researchers in theoretical computer science from around the world.The two main problems that this project will explore are those of proving lower bounds for arithmetic circuits and the problem of polynomial identity testing. These are some of the most central questions in algebraic complexity theory, and this project aims to understand these via the study of bounded-depth arithmetic circuits. The project will also study two other very related problems of polynomial factoring and polynomial reconstruction. In addition, the project will use algebraic techniques to construct new families of error-correcting codes with extremely efficient encodings and with sublinear-time decoding and testing algorithms. In particular, the project will attempt to understand the optimal rate/query complexity tradeoffs in the construction of locally decodable codes and locally testable codes. This project will bring together ideas and tools from a broad array of disciplines and has the potential to have significant practical applications to information storage and retrieval.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.