Skip to main content

Static data structure lower bounds imply rigidity

Author(s): Dvir, Zeev; Golovnev, Alexander; Weinstein, Omri

To refer to this page use:
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 prove that an explicit lower bound of t ≥ ω(log2n) 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 (PNP) 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.
Publication Date: Jun-2019
Citation: Dvir, Zeev, Alexander Golovnev, and Omri Weinstein. "Static data structure lower bounds imply rigidity." Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019): pp. 967-978. doi:10.1145/3313276.3316348
DOI: 10.1145/3313276.3316348
Pages: 967 - 978
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.