BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1041
DTSTAMP:20230914T125948Z
SUMMARY:A Quadratic Lower Bound for Algebraic Branching Programs
DESCRIPTION:Speaker: Prerona Chatterjee\n\nAbstract: \nAbstract: An Algeb
raic Branching Program (ABP) is a layered graph where each edge is labele
d by an affine linear form and the first and the last layer have one vert
ex each\, called the “start” and the “end” vertex respectively. T
he polynomial computed by an ABP is equal to the sum of the weights of al
l paths from the start vertex to the end vertex in the ABP\, where the we
ight of a path is equal to the product of the labels of all the edges on
it. The size of an ABP is the number of vertices in it.\nIn this talk\, we
will see a proof of the following result. Any Algebraic Branching Progra
m (ABP) computing the polynomial $\\sum_{i = 1}^n x_i^n$ has at least $\\
Omega(n^2)$ vertices.\nThis improves upon the lower bound of $\\Omega(n \\
log n)$\, which follows from the classical result of Baur and Strassen [S
tr73\, BS83]\, and extends the results in [Kum19]\, which showed a quadra
tic lower bound for homogeneous ABPs computing the same polynomial.\nThe
talk is based on work done with Mrinal Kumar\, Adrian She and Ben Lee Vol
k.\n
URL:https://www.tcs.tifr.res.in/web/events/1041
DTSTART;TZID=Asia/Kolkata:20200117T160000
DTEND;TZID=Asia/Kolkata:20200117T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR