BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/727
DTSTAMP:20230914T125936Z
SUMMARY:On Isoperimetric Profiles and Computational Complexity
DESCRIPTION:Speaker: Tulasi mohan Molli\n\nAbstract: \nThe isoperiemtric pr
ofile of a Graph is a function that measures\, for an integer k\, is the s
ize of the smallest edge boundary over all sets of vertices of size k.\n\n
Arithmetic circuits and Branching programs are two computational models fo
r computing polynomials. Branching programs can be efficiently simulated b
y Circuits. But\, we don't know if Circuits are strictly more powerful tha
n branching programs.\n\nIn this talk\, we will see the usage of isoperime
tric profiles to prove a sharp super-polynomial separation between monoton
e arithmetic circuits and monotone arithmetic branching programs. This is
a result of Hrubes and Yehudayoff [ICALP 2016].\n\nA key ingredient in the
proof is an accurate analysis of isoperimetric profile of finite full bin
ary trees.\n
URL:https://www.tcs.tifr.res.in/web/events/727
DTSTART;TZID=Asia/Kolkata:20161125T160000
DTEND;TZID=Asia/Kolkata:20161125T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR