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