Stronger Cell Probe Lower Bounds via Local PRGs

In this work we observe a tight connection between three topics: $\mathrm{NC}^{0}$ cryptography, $\mathrm{NC}^{0}$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $\mathrm{NC}^{0}$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is an improvement to the best known static data structure lower bounds, breaking a barrier which has stood for several decades. Prior to our work, the best known lower bound for any explicit problem with M inputs and N queries was $S \geq N^{\frac{1}{t}}(\log M)^{1-\frac{1}{t}}$ for any setting of the word length w (where $S=$ space and $t=$ time) [1]. We prove, for the same class of explicit problems considered in [1], a quadratically stronger space lower bound of the form $S \geq \tilde{\Omega}\left(N^{\frac{2}{t}} \cdot(\log M)^{1-\frac{2}{t}} \cdot 2^{-O(w)}\right)$ for all even $t\gt0$. Second, for the restricted class of nonadaptive bit probe data structures, we improve on this lower bound polynomially: for all odd constants $t\gt1$ we give an explicit problem with N queries and $M \leq N^{O(1)}$ inputs and prove a lower bound $S \geq \Omega\left(N^{\frac{2}{t}+\epsilon_{t}}\right)$ for some constant $\epsilon_{t}\gt0$ depending only on t. Our results build off of an exciting body of work on refuting semi-random CSPs (e.g., [2]–[4]). We then utilize our explicit cell probe lower bounds to obtain the best known unconditional algorithms for $\mathrm{NC}^{0}$ range avoidance: we can solve any instance with stretch $n \mapsto m$ in polynomial time once $m \gg n^{\frac{t}{2}}$ when t is even; with the aid of an NP oracle we can solve any instance with $m\gt n^{\frac{t}{2}-\epsilon}$ when t is odd for some constant $\epsilon\gt 0$. Finally, using our main correspondence we establish some barrier results for obtaining significant improvements to our cell probe lower bounds: (i) near-optimal space lower bounds for an explicit problem with $t=4, w=1$ implies $\mathrm{EXP}^{\mathrm{NP}} \nsubseteq \mathrm{NC}^{1}$; (ii) under the widelybelieved assumption that polynomial-stretch $\mathrm{NC}^{0}$ PRGs exist, there is no natural proof of a lower bound of the form $S \geq N^{\Omega(1)}$ when $t=\omega(1), w=1$.