BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/831
DTSTAMP:20230914T125940Z
SUMMARY:An Exponential Depth-Hierarchy Theorem for Constant-Depth Multiline
ar Circuits
DESCRIPTION:Speaker: Srikanth Srinivasan (Indian Institute of Technology\nD
epartment of Mathmetics\nPowai\nMumbai 400076)\n\nAbstract: \nWe study the
size blow-up that is necessary to convert an algebraic circuit of constan
t product-depth D+1 to one of product-depth D in the multilinear setting.\
nWe show that for every constant $D \\geq 1$\, there is an explicit multil
inear polynomial $P_D$ on $n$ variables that can be computed by a multilin
ear formula of product-depth $D+1$ and size $n$\, but not by any multiline
ar circuit of product-depth $D$ and size less than $\\exp(n^{a_D})$ where
$a_D$ is some constant that depends on $D$.\nThis strengthens a result of
Raz and Yehudayoff (Computational Complexity 2009) who proved a quasipolyn
omial separation\, and a result of Kayal\, Nair and Saha (STACS 2016) who
give an exponential separation in the case$ D=1$.\nI will outline the basi
c ideas behind the proof of this result\nJoint work with Suryajith Chillar
a (CSE IITB)\, Christian Engels (CSE IITB) and Nutan Limaye (CSE IITB).\n
URL:https://www.tcs.tifr.res.in/web/events/831
DTSTART;TZID=Asia/Kolkata:20171205T160000
DTEND;TZID=Asia/Kolkata:20171205T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR