BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/885
DTSTAMP:20230914T125942Z
SUMMARY:On Top Fan-in vs Formal Degree for Depth-3 Arithmetic Circuits
DESCRIPTION:Speaker: Mrinal Kumar (Harvard University\nCenter for Mathemati
cal\nSciences and Applications\nCambridge\nMA 02138\, USA)\n\nAbstract: \n
A well known fact is that there are polynomials of degree 2 (for instance\
, inner product\, or elementary symmetric polynomials of degree 2)\, such
that any representation of these as a sum of product of affine forms requi
res Omega(n) summands\, where n is the total number of variables.\nIn this
talk\, we will see that over the field of complex numbers\, we can approx
imate these polynomials to arbitrary accuracy (in the border complexity se
nse) by a sum of 3 summands\, each of which is a product of affine forms.
Or\, more generally\, *every* homogeneous polynomial of degree d can be ap
proximated by a sum of d+1 terms\, each term being a product of affine for
ms.\nI hope to show the complete proof\, which is an elementary\, simple\,
short and self-contained argument and requires no prior exposure to the n
otion of border computation.\n
URL:https://www.tcs.tifr.res.in/web/events/885
DTSTART;TZID=Asia/Kolkata:20180627T140000
DTEND;TZID=Asia/Kolkata:20180627T150000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR