Complexity seminar
Data structure lower bounds and popular conjectures
Michal Koucký
MFF UK
Friday, 11. March 2022 - 14:00 to 15:30
in IM, rear building, ground floor
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.
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.