Arithmetic Circuits: Algorithms and Complexity

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

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.