Speaker: |
Ramya C. (The Institute of Mathematical Sciences) |

Organiser: |
Raghuvansh Saxena |

Date: |
Tuesday, 11 Jun 2024, 16:00 to 17:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

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.