Static data structure lower bounds imply rigidity

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of t ≥ ω(log 2 n ) on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small linear space ( s = (1+) 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 results further assert that polynomial ( t ≥ n δ ) data structure lower bounds against near-optimal space, would imply super-linear circuit lower bounds for log-depth linear circuits (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 results rely on a new connection between the “inner” and “outer” dimensions of a matrix (Paturi and Pudlák, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest.

Authors

• Zeev Dvir
• Alexander Golovnev
• Omri Weinstein

Keywords

• circuit lower bound
• codes
• data structures
• rigidity