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