Speaker: |
Prerona Chatterjee |

Organiser: |
Anamay Tengse |

Date: |
Friday, 17 Jan 2020, 16:00 to 17:30 |

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

(Scan to add to calendar)

In this talk, we will see a proof of the following result. Any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices.

This improves upon the lower bound of $\Omega(n \log n)$, which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results in [Kum19], which showed a quadratic lower bound for homogeneous ABPs computing the same polynomial.

The talk is based on work done with Mrinal Kumar, Adrian She and Ben Lee Volk.