Time-Space Trade-Offs for Predecessor Search

Mihai Patrascu, Mikkel Thorup

We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be…