AF: Small: Algebraic Methods in Codes and Computation

AF：小：代码和计算中的代数方法

• 批准号: 1909683
• 负责人: Eric Allender
• 金额: $ 30万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2023-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909683&HistoricalAwards=false
• 关键词: AF; Small; Algebraic; Methods; Codes

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.

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

项目成果

One-Way Functions and a Conditional Variant of MKTP

单向函数和 MKTP 的条件变体

• DOI: 10.4230/lipics.fsttcs.2021.7
• 发表时间: 2021-11
• 期刊: Leibniz international proceedings in informatics
• 作者: Allender, Eric;Cheraghchi, Mahdi;Myrisiotis, Dimitrios;Tirumala, Harsha;Volkovich, Ilya
• 通讯作者: Volkovich, Ilya

Guest Column: Parting Thoughts and Parting Shots (Read On for Details on How to Win Valuable Prizes!

客座专栏：离别感想与别离镜头（请继续阅读，了解如何赢得宝贵奖品的详细信息！

• DOI: 10.1145/3586165.3586175
• 发表时间: 2023-02
• 期刊: ACM SIGACT News
• 作者: Allender; Eric
• 通讯作者: Eric

Depth-First Search in Directed Planar Graphs, Revisited

重新审视有向平面图中的深度优先搜索

• DOI: 10.4230/lipics.mfcs.2021.7
• 发表时间: 2021-01
• 期刊: Leibniz international proceedings in informatics
• 作者: Allender, Eric;Chauhan, Archit;Datta, Samir
• 通讯作者: Datta, Samir

Cryptographic Hardness Under Projections for Time-Bounded Kolmogorov Complexity

时限柯尔莫哥洛夫复杂度预测下的密码硬度

• DOI: 10.4230/lipics.isaac.2021.54
• 发表时间: 2021-11
• 期刊: Leibniz international proceedings in informatics
• 作者: Allender, Eric;Gouwar, John;Hirahara, Shuichi;Robelle, Caleb
• 通讯作者: Robelle, Caleb

DEEP-FRI: Sampling Outside the Box Improves Soundness

DEEP-FRI：开箱即用的采样提高了稳定性

• 发表时间: 2020-01
• 期刊: ITCS 2020
• 作者: Ben;Goldberg, L;Kopparty, S;Saraf, S
• 通讯作者: Saraf, S