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.
