Lower Bounds for Planar Arithmetic Circuits

Raghuvansh Saxena
Tuesday, 11 Jun 2024, 16:00 to 17:00
A-201 (STCS Seminar Room)

Arithmetic circuits are a natural computational model for computing multivariate polynomials over a field. Planar arithmetic circuits are circuits whose underlying graph is planar. The size of a circuit  which is the number of vertices in the underlying graph is a fundamental parameter concerning circuits. In this talk, we will prove  a superlinear lower bound on the size of planar arithmetic circuits computing an explicit bilinear form. More generally, we will walk-through the algebraic complexity of bilinear forms. Furthermore, Baur and Strassen(1983) showed that all the first order partial derivatives of a polynomial can be simultaneously computed with only a constant factor blow-up in size. We observe that an analogous statement does not hold in the case of planar circuits.

This talk is based on joint work with Pratik Shastri(IMSc).

Short Bio:

Ramya is currently a faculty member in the Theoretical Computer Science group at the Institute of Mathematical Sciences(IMSc), Chennai.
Prior to this, she was a faculty member at the Chennai Mathematical Institute(CMI). Before joining CMI, she was a postdoctoral fellow at  STCS, TIFR, Mumbai during 2019-2021.
She obtained her PhD from IIT Madras in 2019. Her research is centered around Computational Complexity Theory, particularly problems with an algebraic flavor.