BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/992
DTSTAMP:20230914T125946Z
SUMMARY:Lowerbound against homogeneous multilinear formulas
DESCRIPTION:Speaker: Prerona Chatterjee\n\nAbstract: \nAbstract: A polynom
ial is said to be multilinear if the individual degree of every variable i
s at most one in any monomial\; and is said to be homogeneous if every mon
omial in it has the same degree. Many polynomials of interest (like the de
terminant or the permanent of a symbolic matrix) are homogeneous multiline
ar polynomials. An algebraic formula is a model for computing polynomial
s and is said to be a homogeneous multilinear one if every gate in it comp
utes a homogeneous multilinear polynomial. Hrubes and Yehudayoff (in their
2011 paper) showed that any polynomial that is computed by a homogeneous
multilinear formula has a very special decomposition (called the log-produ
ct decomposition) and used it to give a lowerbound against this model. In
today's talk\, we will see the full proof of this lowerbound.\n
URL:https://www.tcs.tifr.res.in/web/events/992
DTSTART;TZID=Asia/Kolkata:20190913T171500
DTEND;TZID=Asia/Kolkata:20190913T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR