Data Structures Lower Bounds and Popular Conjectures
From MaRDI portal
Abstract: 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.
Recommendations
- Lower bounds for oblivious data structures
- Bit-probe lower bounds for succinct data structures
- Bit-probe lower bounds for succinct data structures
- Lower bounds for data structures with space close to maximum imply circuit lower bounds
- Locally finite properties of data structures and their computation
- Data structure lower bounds for document indexing problems
- Problems in data structures and algorithms
- scientific article; zbMATH DE number 1775407
- scientific article; zbMATH DE number 4049010
Cited in
(6)- scientific article; zbMATH DE number 17540 (Why is no real title available?)
- scientific article; zbMATH DE number 7250167 (Why is no real title available?)
- Static data structure lower bounds imply rigidity
- Revisiting time-space tradeoffs for function inversion
- On the power of adaptivity for function inversion
- A general technique for searching in implicit sets via function inversion
This page was built for publication: Data Structures Lower Bounds and Popular Conjectures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075928)
