Abstract
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 of data structures in the restricted group 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 super-linear circuit lower bounds 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.