Abstract
Proving lower bounds on the time-space tradeoff of data structures has been a long and active research endeavor for several decades. In a static data structure problem, the goal is to preprocess a database of n elements into minimum space s (>= n), so that queries q \in Q on the input database can be answered in time t. The only super-constant lower bound on the query time t >= \Omega(logn) we know for such data structures is for the regime of linear space s=O(n).
We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we show that an explicit lower bound of t >= \omega(log^2 n) on the query time data structures in the linear model, even against arbitrarily small linear space (s= (1+eps)*n), would already imply a semi-explicit (P^NP) construction of rigid matrices with significantly better parameters than the current state of art [Alon, Panigrahy, and Yekhanin, 2009]. Our result also proves that stronger data structure lower bounds (against *polynomial* space) would imply a super-linear circuit lower bound for log-depth linear circuits (which would close a four-decade open question). In the succinct space regime (s=n+o(n)), we show that any improvement on current cell-probe lower bounds in the linear model would also imply new rigidity bounds. Our main result relies on a new connection between the "inner" and "outer" dimensions of a matrix (Pudlak and Paturi, 2006).
Based on a joint work with Zeev Dvir and Omri Weinstein.