BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1125
DTSTAMP:20230914T125951Z
SUMMARY:Network Coding Conjecture implies Data Structure Lower Bounds
DESCRIPTION:Speaker: Pavel Dvorak (Charles University\, Prague)\n\nAbstract
 : \nNetwork coding conjecture (NCC) by Li and Li asserts that network codi
 ng for undirected graphs does not bring any advantage over multicommodity 
 flows. Recently\, NCC was used to prove a conditional lower bound for sort
 ing algorithms with external memory [Farhadi et al.\, STOC 2019]\, circuit
 s for multiplication [Afshani et al.\, ICALP 2019]\, and circuits for sort
 ing [Asharov et al.\, SODA 2021]. We use a technique of Farhadi et al. to 
 prove an NCC-based lower bound for non-adaptive data structures for functi
 on inversion\, polynomial evaluation\, and polynomial interpolation. This 
 is a joint work with Michal Koucký\, Karel Král and Veronika Slívová.\
 n
URL:https://www.tcs.tifr.res.in/web/events/1125
DTSTART;TZID=Asia/Kolkata:20210415T174500
DTEND;TZID=Asia/Kolkata:20210415T184500
END:VEVENT
END:VCALENDAR