Derandomization of Cell Sampling

Abstract

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 $s\ge \tilde{\Omega }\left(n\cdot (\frac{m}{n}{)}^{1/t}\right)$. In this work, we improve this bound for non-adaptive data structures to $s\ge \tilde{\Omega }\left(n\cdot (\frac{m}{n}{)}^{1/(t-1)}\right)$ for all $t\ge 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 ${\mathbb{F}}_2$ and Siegel's bound $s\ge \tilde{\Omega }(\sqrt{mn})$ over other finite fields.