Derandomization of Cell Sampling
Alexander Golovne, Tom Gur, Igor Shinkar · Society for Industrial and Applied Mathematics eBooks · 2023
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 possible queries such that every data structure that answers queries by probing t memory cells requires space . In this work, we improve this bound for non-adaptive data structures to for all t ≥ 2. For t = 2, we give a lower bound of s > m — o (m), improving on the bound s > m/2 recently proved by Viola over