BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1404
DTSTAMP:20240307T103500Z
SUMMARY:A superpolynomial lower bound against weighted homogeneous formulas
DESCRIPTION:Speaker: Varun Ramanathan (TIFR)\n\nAbstract: \nOn the path to 
 proving lower bounds against general arithmetic/algebraic models of comput
 ation\, a longstanding open problem is to construct explicit polynomials t
 hat are superpolynomially hard for arithmetic formulas. Even for the poten
 tially weaker model of homogeneous formulas\, we do not have such strong l
 ower bounds. Recently\, Fournier\, Limaye\, Srinivasan and Tavenas gave a 
 superpolynomial lower bound against a related model of computation called 
 weighted homogeneous formulas\, thus getting us a little (or a lot?) close
 r to homogeneous formula lower bounds. The proof goes via a relatively sim
 ple application of the probabilistic method. We will try and understand th
 is proof. There are no prerequisites\, besides the vague notion of mathema
 tical maturity.\n
URL:https://www.tcs.tifr.res.in/web/events/1404
DTSTART;TZID=Asia/Kolkata:20240308T143000
DTEND;TZID=Asia/Kolkata:20240308T153000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR