BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/635
DTSTAMP:20230914T125932Z
SUMMARY:Lower Bounds for Shallow Circuits
DESCRIPTION:Speaker: Ramprasad Saptharishi (Tel Aviv University\nTel Aviv-Y
afo\nIsrael)\n\nAbstract: \nAbstract: Over the last 3--4 years\, there has
been a sudden surge of results in arithmetic circuit lower bounds\, speci
fically for shallow circuits (depth 3 or 4). The main motivation for study
ing depth-4 circuits is a result of Agrawal and Vinay (and subsequent stre
ngthening by Koiran and Tavenas) that states that any arithmetic circuit o
f size s that computes an n-variate degree d polynomial can be simulated b
y a structured homogeneous depth-4 circuit of size n^{Omega (sqrt{d})}. Fl
ipping this around\, this implies that if we can find an explicit polynomi
al that requires such structured depth-4 circuits of size n^{omega(sqrt {d
})}\, then we would have proved lower bounds for general arithmetic circui
ts!\n\nIn 2013\, in a joint work with Gupta\, Kamath and Kayal\, we showed
a lower bound of 2^{Omega (sqrt{d})} for the dxd permanent or determinant
using a technique called 'shifted partial derivatives' (introduced by [Ka
yal]). Subsequent to this result\, there has been a sequence of improvemen
ts of various sorts (improving the lower bound\, or dealing with a larger
circuit class etc.) thereby improving our understanding of depth four circ
uits. The current state of the art is an n^{Omega(sqrt{d})} lower bound fo
r the class of homogeneous depth-4circuits with no structural restrictions
[Kayal-Limaye-Saha-Srinivasan\, Kumar-Saraf].\n\nIn this talk\, I shall g
ive a brief overview of the progress made in the last 3 years and put the
various results in context. Then\, I shall present a recent work with Mrin
al Kumar that gives an exponential lower bound for depth-5 circuits over s
mall finite fields that combines the techniques developed so far with an o
ld result of Grigoriev-Karpinski for depth-3 lower bounds.\n
URL:https://www.tcs.tifr.res.in/web/events/635
DTSTART;TZID=Asia/Kolkata:20151123T160000
DTEND;TZID=Asia/Kolkata:20151123T170000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR