BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Nutan Limaye (IT University of Copenhagen)
DTSTART:20211013T170000Z
DTEND:20211013T180000Z
DTSTAMP:20260423T021015Z
UID:TCSPlus/30
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/TCSPlus/30/"
 >Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits</a>\nby
  Nutan Limaye (IT University of Copenhagen) as part of TCS+\n\n\nAbstract\
 n"Every multivariate polynomial P(X) can be written as a sum of monomials\
 , i.e. a sum of products of variables and field constants. In general\, th
 e size of such an expression is the number of monomials that have a non-ze
 ro coefficient in P.\n\nWhat happens if we add another layer of complexity
 \, and consider sums of products of sums (of variables and field constants
 ) expressions? Now\, it becomes unclear how to prove that a given polynomi
 al P(X) does not have small expressions. In this result\, we solve exactly
  this problem.\n\nMore precisely\, we prove that certain explicit polynomi
 als have no polynomial-sized "Sigma-Pi-Sigma" (sums of products of sums) r
 epresentations. We can also show similar results for Sigma-Pi-Sigma-Pi\, S
 igma-Pi-Sigma-Pi-Sigma and so on for all "constant-depth" expressions. \n\
 nThe talk is based on a joint work of Nutan Limaye\, Srikanth Srinivasan\,
  and Sébastien Tavenas."\n
LOCATION:https://researchseminars.org/talk/TCSPlus/30/
END:VEVENT
END:VCALENDAR