TY - GEN
T1 - Static data structure lower bounds imply rigidity
AU - Dvir, Zeev
AU - Golovnev, Alexander
AU - Weinstein, Omri
N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/6/23
Y1 - 2019/6/23
N2 - 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ák, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest.
AB - 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ák, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest.
KW - Circuit lower bound
KW - Codes
KW - Data structures
KW - Rigidity
UR - http://www.scopus.com/inward/record.url?scp=85068766763&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068766763&partnerID=8YFLogxK
U2 - 10.1145/3313276.3316348
DO - 10.1145/3313276.3316348
M3 - Conference contribution
AN - SCOPUS:85068766763
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 967
EP - 978
BT - STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
A2 - Charikar, Moses
A2 - Cohen, Edith
PB - Association for Computing Machinery
T2 - 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
Y2 - 23 June 2019 through 26 June 2019
ER -