@inproceedings{11113684ff2e4277955ff0f36df096b7,

title = "Static data structure lower bounds imply rigidity",

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 ≥ ω(log2 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 (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{\'a}k, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest.",

keywords = "Circuit lower bound, Codes, Data structures, Rigidity",

author = "Zeev Dvir and Alexander Golovnev and Omri Weinstein",

year = "2019",

month = jun,

day = "23",

doi = "10.1145/3313276.3316348",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "967--978",

editor = "Moses Charikar and Edith Cohen",

booktitle = "STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing",

note = "51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 ; Conference date: 23-06-2019 Through 26-06-2019",

}