ECCC-Report TR18-188https://eccc.weizmann.ac.il/report/2018/188Comments and Revisions published for TR18-188en-usThu, 14 Feb 2019 01:36:38 +0200
Revision 2
| Static Data Structure Lower Bounds Imply Rigidity |
Zeev Dvir,
Alexander Golovnev,
Omri Weinstein
https://eccc.weizmann.ac.il/report/2018/188#revision2We 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 \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small linear space $(s= (1+\varepsilon)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\geq n^{\delta}$) 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 Pudlak, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest. Thu, 14 Feb 2019 01:36:38 +0200https://eccc.weizmann.ac.il/report/2018/188#revision2
Revision 1
| Static Data Structure Lower Bounds Imply Rigidity |
Zeev Dvir,
Alexander Golovnev,
Omri Weinstein
https://eccc.weizmann.ac.il/report/2018/188#revision1We 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 \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small linear space $(s= (1+\varepsilon)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\geq n^{\delta}$) 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 Pudlak, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest. Wed, 14 Nov 2018 21:29:29 +0200https://eccc.weizmann.ac.il/report/2018/188#revision1
Paper TR18-188
| Static Data Structure Lower Bounds Imply Rigidity |
Zeev Dvir,
Alexander Golovnev,
Omri Weinstein
https://eccc.weizmann.ac.il/report/2018/188We 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 \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small linear space $(s= (1+\varepsilon)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\geq n^{\delta}$) 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 Pudlak, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest. Wed, 07 Nov 2018 03:05:01 +0200https://eccc.weizmann.ac.il/report/2018/188