BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1388
DTSTAMP:20240125T064217Z
SUMMARY:New Lower Bounds for Set-Multilinear Branching Programs
DESCRIPTION:Speaker: Mr. Deepanshu Kush (University of Toronto)\n\nAbstract
 : \nIn this talk\, we will discuss new lower bounds for the model of sum 
 of ordered set-multilinear algebraic branching programs. The significance 
 of these lower bounds is underscored by the recent work of Bhargav\, Dwive
 di\, and Saxena (2023)\, which showed that super-polynomial lower bounds a
 gainst this model -- for a set-multilinear polynomial of sufficiently low 
 degree -- would imply super-polynomial lower bounds against general ABPs\
 , thereby resolving Valiant's longstanding conjecture that the permanent p
 olynomial cannot be computed efficiently by ABPs. We will discuss our new 
 results which "almost" meet this low-degree demand. This is joint work wit
 h Prerona Chatterjee\, Shubhangi Saraf\, and Amir Shpilka. \nShort Bio:\n
 Deepanshu Kush is a fourth year PhD student in Computer Science at the Uni
 versity of Toronto\, where he is advised by Shubhangi Saraf. His research 
 interests are broadly in theoretical computer science and related areas of
  math with a focus on computational complexity theory.\n
URL:https://www.tcs.tifr.res.in/web/events/1388
DTSTART;TZID=Asia/Kolkata:20240212T113000
DTEND;TZID=Asia/Kolkata:20240212T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR