Derandomization of Cell Sampling

Alexander Golovnev, Tom Gur, Igor Shinkar

Since 1989, the best known lower bound on static data structures was Siegel's classical cell sampling lower bound. Siegel showed an explicit problem with $n$ inputs and $m$ possibl…