IMSc Webinar

Algebraic Complexity Theory: A gripping tale of two polynomials.

C Ramya

TIFR

Webinar: join at https://zoom.us/j/9232575195?pwd=OGgxV29CQ1RaUDd5N3NQNWluMDhydz09 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 compute 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, **circuit reconstruction *and* matrix rigidity*.