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á.
