Stronger Cell Probe Lower Bounds via Local PRGs

In this work, we develop a new method for proving lower bounds for static data structures in the classical cellprobe model of Yao. Our methods give the strongest known lower bounds for any explicit problem in this model (quadratically stronger for space as a function of time) and break a barrier which has stood for a few decades. Our lower bounds are based on a new connection we establish between the static cell probe model and NC0 generators, which have been studied extensively in cryptography and more recently in the context of “range avoidance.

Joint with Toniann Pitassi (Columbia University) and Russell Impagliazzo (UC San Diego).