Charles University, Prague
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á.