Computer Science Seminar
Date: Wednesday, 26 June 2024
Time: 2:00 – 3:00 PM.
Venue: Seminar Hall
Read-once Algebraic branching programs and commuting matrices
Anamay Tengse
NISER.
26-06-24

---

Abstract

A simple (but well-studied) model for computing polynomials is that of 'sums of powers of linear forms'. It can be shown that any polynomial that can be expressed efficiently by this model has a small 'dimension of partial derivatives', a measure introduced by Nisan and Wigderson (1996). The converse: whether every polynomial with a small dimension of partial derivatives can be efficiently computed by this model, is an interesting open question. Dimension of partial derivatives, and its variants, have been a popular tool for proving algebraic circuit lower bounds, all the way up to the recent breakthroughs, thus adding more intrigue to the question about the converse.

In this talk, we will see a somewhat surprising connection between this question and yet another simple algebraic model of read-once algebraic branching programs (ROABPs). We will also see how partial derivatives of a polynomial can be used to build explicit ROABPs for it. Both these results are part of my joint works with C Ramya (IMSc, Chennai) and Vishwas Bhargava (University of Waterloo, Canada).