|
Date: 26 Jan; Time : 9 pm. Topic: A talk by Ramya C. Time: Jan 26, 2021 9:00 PM Mumbai, Kolkata, New Delhi Algebraic Complexity Theory: A gripping tale of two polynomials Ramya C. TIFR. 26-01-21 Abstract We live in a world where the quest for efficient computation is indispensable. Understanding the amount of resource (e.g., time, space) required to solve a given computational problem on models of computation (e.g., Turing machines) underlies much of Computational Complexity Theory. In this talk, we will primarily be interested in the complexity of computing polynomials by arithmetic circuits which are a natural computational model for polynomials. The number of arithmetic operations needed to computed a polynomial is captured by the size of an arithmetic circuit computing it. While the symbolic determinant polynomial can be computed by polynomial size arithmetic circuits, Valiant(1979) conjectured that the symbolic permanent cannot be. Despite consistent efforts, the best-known circuit size lower bound is barely super-linear in the number of variables. Given that determinant, permanent are all multilinear polynomials, understanding multilinear computation is of significant importance. We will briefly discuss some results in this direction. Most known lower bounds can be unified under the framework of algebraically natural proofs introduced by Grochow, Kumar, Saks, Saraf(2017) and Forbes, Shpilka, Volk(2018). We will review this natural recipe for proving arithmetic circuit size lower bounds. While some believe that this framework cannot be extended to settle the truth of Valiant’s conjecture, some of our recent results highlight the existence of natural lower bound techniques for proving lower bounds against certain rich subclasses of arithmetic circuits. En route, we will briefly discuss other interesting computational problems concerning polynomials such as polynomial identity testing and circuit reconstruction.
|
