|
10:30, Seminar Hall On the computation of multilinear polynomials ---A walk-through Algebraic Complexity Theory and Beyond C Ramya Chennai Mathematical Institute. 15-03-19 Abstract Polynomials are the most fundamental objects in algebra and it is compelling to understand the complexity of computing polynomials. That is, given a polynomial we would like to understand the number of arithmetic operations needed to compute it. Towards this end, Leslie G. Valiant in 1979 introduced arithmetic circuits as a model for computing polynomials. We will primarily be interested in size of an arithmetic circuit computing f which is the number of arithmetic operations needed to compute the polynomial f. Algebraic complexity theory is the study of intrinsic complexity of algebraic computation. Broadly speaking, the main tasks in algebraic computation can be classified into: -- Understanding the complexity of computing polynomials -- Solving computational problems concerning polynomials In the first part of the talk, we will understand multilinear polynomials such as the determinant and permnanent through a computational lens. While the determinant polynomial is known to be efficiently computable, Valiant (1979) conjectured that the permanent polynomial cannot be computed efficiently by arithmetic circuits. Subsequent to Valiant's conjecture, proving size lower bounds for arithmetic circuits computing permanent have been of much interest. While the answer to Valiant's conjecture seems to be a distance dream, recent research has focused on several restricted classes of arithmetic circuits. In this talk, we aim at understanding the structure of multilinear formulas and syntactic multilinear branching programs which are restricted classes of arithmetic circuits for computing multilinear polynomials. The best known size lower bound for multilinear circuits is barely quadratic in the number of variables. Proving super-polynomial size lower bounds for such circuits computing an explicit multilinear polynomial is a challenging problem in Algebraic Complexity Theory. In this talk, we aim to understand the structure of these circuits and outline possible approaches to prove super-polynomial lower bounds for multilinear branching programs. In the second part of the talk, we study the computational problem of polynomial equivalence - testing if two given polynomials are the same upto a linear change of coordinates. This is a hard computational problem in its full generality and we will review the tractability of several special cases with special focus on the Vandermonde polynomials. It is interesting to note that polynomials that are equivalent upto a linear transformation have similar computational complexity in standard models of computation such as arithmetic circuits. Most of the results presented in this talk are a joint work with B.V.Raghavendra Rao, IIT Madras.
|
