Arithmetic Circuits: Algorithms and Complexity

算术电路：算法和复杂性

• 批准号: RGPIN-2022-04250
• 负责人: Saraf, Shubhangi
• 金额: $ 4.01万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758696
• 关键词: Arithmetic; Circuits; Algorithms; Complexity

Arithmetic circuits are one of the most natural models for algebraic computation. Indeed many fundamental algebraic tasks such as matrix multiplication, determinant computation, computing fast fourier transforms etc can be captured by efficient algorithms via arithmetic circuits. Perhaps the most fundamental open problem in algebraic complexity theory is the VP vs VNP question, which is the algebraic analog of the P vs NP question. It attempts at understanding which algebraic problems do not have efficient algebraic algorithms. This project will study the complexity of arithmetic circuits and attempt to make progress on the VP vs VNP question via studying lower bounds and other closely related questions for arithmetic circuits. In recent years there has been great deal of interest in understanding bounded depth arithmetic circuits. Indeed we know that strong enough lower bounds for just constant depth arithmetic circuits would give superpolynomial lower bounds for general circuits and hence separate VP from VNP. Studying bounded depth circuits will be an important focus of this project. In addition to studying lower bounds, this project will investigate other closely related questions such as deterministic polynomial identity testing, polynomial factoring and the problem of learning or reconstructing arithmetic circuits. Previous work by the PI has developed several techniques to study these questions, including incidence geometry methods, rank bounds and the use of partial derivatives. These have led to the first exponential lower bound for depth 4 arithmetic circuits over all fields, efficient factoring algorithms for sparse polynomials and the first polynomial time learning algorithms for low rank tensors. In this proposal the PI will develop new techniques to study the major open questions in algebraic complexity theory. Studying these questions will provide deep insight into the structure and power of algebraic computation which underlies several fundamental results in theoretical computer science. Additionally the project will also harness the algebraic techniques developed for other interesting applications in the constructing of error correcting codes and other questions in pseudorandomness. Mentoring and training of young researchers is an important part of the educational component of the project. Additionally, the PI will co-organize the Women in Theory workshop in the summer of 2022 and again in 2024, which will bring together women researchers in theoretical computer science from around the world.

算术电路是代数计算最自然的模型之一。事实上，许多基本的代数任务，如矩阵乘法，行列式计算，计算快速傅立叶变换等，可以通过有效的算法通过算术电路捕获。代数复杂性理论中最基本的开放问题可能是VP vs VNP问题，它是P vs NP问题的代数类比。它试图了解哪些代数问题没有有效的代数算法。本计画将研究算术电路的复杂性，并尝试透过研究算术电路的下界及其他相关问题，在VP与VNP问题上取得进展。近年来，人们对有界深度算术电路的理解产生了极大的兴趣。事实上，我们知道，对于恒定深度算术电路，足够强的下界将给出一般电路的超多项式下界，从而将VP与VNP分开。研究有界深度电路将是本项目的一个重要重点。除了研究下界，本项目还将研究其他密切相关的问题，如确定性多项式身份测试，多项式分解和学习或重建算术电路的问题。PI以前的工作已经开发了几种技术来研究这些问题，包括关联几何方法，秩界和偏导数的使用。这些导致了所有领域的深度4算术电路的第一个指数下界，稀疏多项式的有效因子分解算法和低秩张量的第一个多项式时间学习算法。在这个提议中，PI将开发新的技术来研究代数复杂性理论中的主要开放问题。研究这些问题将提供深入了解代数计算的结构和能力，这是理论计算机科学中几个基本结果的基础。此外，该项目还将利用为其他有趣的应用程序开发的代数技术，在构建纠错码和其他问题的伪随机性。指导和培训青年研究人员是该项目教育部分的一个重要组成部分。此外，PI将在2022年夏天和2024年再次共同组织理论女性研讨会，该研讨会将汇集来自世界各地的理论计算机科学女性研究人员。