Arithmetic Circuits: Algorithms and 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.