Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Toronto

$55,000.00

Arithmetic Circuits: Algorithms and Complexity

FY 2022-23

Summary
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.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2022-04250
Name nom
Saraf, Shubhangi
Department département
Mathematics (St. George Campus) - Mathematics (St. George Campus)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2022
Award amount
55000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:1
Partie
1
Nb partie
5
Application title
Arithmetic Circuits: Algorithms and Complexity
Application summary
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.