  In this paper, we investigate the relative power of several conjectures that
attracted recently lot of interest. We establish a connection between the
Network Coding Conjecture (NCC) of Li and Li and several data structure like
problems such as non-adaptive function inversion of Hellman and the
well-studied problem of polynomial evaluation and interpolation. In turn these
data structure problems imply super-linear circuit lower bounds for explicit
functions such as integer sorting and multi-point polynomial evaluation.
