Tata Institute of Fundamental Research
Network Coding Conjecture implies Data Structure Lower Bounds
STCS Seminar
Speaker:
Pavel Dvorak (Charles University, Prague)
Organiser:
Arkadev Chattopadhyay
Date:
Thursday, 15 Apr 2021, 17:45 to 18:45
Venue:
(Scan to add to calendar)
Abstract:
Network coding conjecture (NCC) by Li and Li asserts that network coding for undirected graphs does not bring any advantage over multicommodity flows. Recently, NCC was used to prove a conditional lower bound for sorting algorithms with external memory [Farhadi et al., STOC 2019], circuits for multiplication [Afshani et al., ICALP 2019], and circuits for sorting [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 function inversion, polynomial evaluation, and polynomial interpolation. This is a joint work with Michal Koucký, Karel Král and Veronika Slívová.
| Speaker: | Pavel Dvorak (Charles University, Prague) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Thursday, 15 Apr 2021, 17:45 to 18:45 |
| Venue: |
(Scan to add to calendar)
Abstract:
Network coding conjecture (NCC) by Li and Li asserts that network coding for undirected graphs does not bring any advantage over multicommodity flows. Recently, NCC was used to prove a conditional lower bound for sorting algorithms with external memory [Farhadi et al., STOC 2019], circuits for multiplication [Afshani et al., ICALP 2019], and circuits for sorting [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 function inversion, polynomial evaluation, and polynomial interpolation. This is a joint work with Michal Koucký, Karel Král and Veronika Slívová.