Room 327

Lower bounds for Planar Arithmetic Circuits

Pratik Shastri

IMSc

Arithmetic circuits are natural well studied models for
computing polynomials. In this talk, we will look at planar arithmetic
circuits. These are circuits whose underlying graph is planar. In
particular, we will prove an Omega(n^2) lower bound on the size of
read once planar arithmetic circuits computing explicit bilinear forms
on 2n variables and an Omega(n\log n) lower bound on the size of
(general) planar arithmetic circuits computing these same bilinear
forms. Bilinear forms are an important class of degree two polynomials
of the form y^{T}Ax where y and x are vectors of n variables each and
A is an n x n matrix. As a consequence, we get an Omega(n\log n) lower
bound on the size of arithmetic formulas computing these bilinear
forms. This is the first such lower bound on the formula complexity of
an explicit bilinear form. We will also look planar, multi output
computation and prove better lower bounds in the multi-output case.
(Joint work with C Ramya, to appear in ITCS 2024)