IMSc Webinar

On computing multilinear polynomials using depth four circuits of bounded individual degree.

Suryajith Chillara

Univ. of Haifa

Webinar: join at https://meet.google.com/xsd-ffto-nqc One of the central themes in the study of Algebraic Complexity Theory is to prove lower bounds against general arithmetic circuits which compute “explicit” polynomials. Owing to the slow progress towards this, restricted models of circuits were studied -- (1) Bounded individual degree with respect to each of its variables, and (2) Bounded depth. As it is the case that many of the polynomials of interest are in fact multilinear, a restriction of 'bounded individual degree' is natural. In the recent past strong lower bounds were shown against formulas and (bounded depth) circuits of individual degree at most $1$. A natural extension to these results is to study the complexity of computing multilinear polynomials by formulas and circuits of bounded individual degree $r$ for a value greater than $1$. In this talk, we shall see that that for all $1\leq r \leq n^{a}$ (for a fixed constant $a$), any “syntactic” depth four circuit of bounded individual degree $r$ computing the Iterated Matrix Multiplication polynomial (denoted by $IMM_{n,d}$) must have size $n^{\Omega(\sqrt{d})}$ when $d\leq n^{b}$ (for a fixed constant $bd$. This talk assumes no relevant background. We will introduce the model of computation, make explicit the motivation to study the computation of multilinear polynomials by circuits of bounded individual degree and briefly list relevant results. Link to relevant resources: 1. https://eccc.weizmann.ac.il/report/2020/033/revision/1/download, 2. https://eccc.weizmann.ac.il/report/2020/032/revision/2/download