BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/949
DTSTAMP:20230914T125944Z
SUMMARY:Lower Bounds for General Algebraic Circuits
DESCRIPTION:Speaker: Prerona Chatterjee\n\nAbstract: \nAbstract: The be
st known lower bound for general algebraic circuits was given by Baur and
Strassen [BS83]. They showed that there exists an explicit n-variate\,
degree d polynomial such that the smallest fan-in 2 circuit computing it
requires size Omega(n log d).\nHowever\, when d is constant\, the above re
sult only gives a linear lower bound. In this setting\, Raz [Raz08] gave
a super-linear lower bound of the following form. He showed that for any
natural number d\, there exists an explicit n-variate polynomial of degre
e O(d) such that the smallest depth-d circuit computing it requires size
$n^{1 + Omega(1/d)}$.\nIn this talk\, we will quickly go over the proof i
dea of the result by Baur-Strassen and then focus on Raz's super-linear l
ower bound for bounded depth circuits.\n
URL:https://www.tcs.tifr.res.in/web/events/949
DTSTART;TZID=Asia/Kolkata:20190315T171500
DTEND;TZID=Asia/Kolkata:20190315T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR