Algebraic complexity aims at understanding the computational aspects of algebraic objects such as multivariate polynomials, tensors etc. The primary focus in this field has been the study of multivariate polynomials, and its hardness based on the number of addition/multiplication operations required to compute it (i.e. via `algebraic circuits'). This is a quest to answer the ``VP vs VNP'' question, an algebraic analogue of the classical ``P vs NP'' question and is a fundamental open problem in algebraic complexity.These questions about multivariate polynomial broadly fall in one of the following categories:Lower bounds: Can we find explicit polynomials that cannot be computed by small algebraic circuits?Polynomial Identity Testing: Given an algebraic circuit C, can we test efficiently if the circuit C is computing the zero polynomial? (Or equivalently, can we test if two circuits C_1 and C_2 are computing the same polynomial?)Reconstruction: Given blackbox access to a circuit C, can we...
Description