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年夏天共同组织“Women in Theory”研讨会，该研讨会将汇集来自世界各地的理论计算机科学领域的女性研究人员。该项目将探讨的两个主要问题是证明算术电路的下界和多项式恒等式测试问题。这些是代数复杂性理论中最核心的问题，本项目旨在通过研究有界深度算术电路来理解这些问题。该项目还将研究其他两个非常相关的问题，多项式分解和多项式重构。此外，该项目将使用代数技术来构建新的纠错码家族，这些纠错码具有非常有效的编码和次线性时间解码和测试算法。特别是，该项目将试图了解最佳的速率/查询复杂度的权衡在本地可解码的代码和本地可测试的代码的建设。该项目将汇集来自广泛学科的想法和工具，并有可能在信息存储和检索方面有重要的实际应用。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的知识价值和更广泛的影响审查标准进行评估来支持。

项目成果

Cryptographic hardness under projections for time-bounded Kolmogorov complexity

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

• DOI: 10.1016/j.tcs.2022.10.040
• 发表时间: 2022
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Allender, Eric;Gouwar, John;Hirahara, Shuichi;Robelle, Caleb
• 通讯作者: Robelle, Caleb

One-Way Functions and a Conditional Variant of MKTP

单向函数和 MKTP 的条件变体

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

Fast, algebraic multivariate multipoint evaluation in small characteristic and applications

• DOI: 10.1145/3519935.3519968
• 发表时间: 2021-11
• 期刊: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
• 作者: Vishwas Bhargava;Sumanta K Ghosh;Mrinal Kumar;C. K. Mohapatra

Depth-first search in directed planar graphs, revisited

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

• DOI: 10.1007/s00236-022-00425-1
• 发表时间: 2022
• 期刊: Acta Informatica
• 影响因子: 0.6
• 作者: Allender, Eric;Chauhan, Archit;Datta, Samir
• 通讯作者: Datta, Samir

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

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

• DOI: 10.1145/3586165.3586175
• 发表时间: 2023
• 期刊: ACM SIGACT News
• 作者: Allender, Eric