ECCC-Report TR18-186https://eccc.weizmann.ac.il/report/2018/186Comments and Revisions published for TR18-186en-usTue, 13 Nov 2018 20:06:58 +0200
Revision 1
| Lower bounds for data structures with space close to maximum imply circuit lower bounds |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/186#revision1Let $f:\{0,1\}^{n}\to\{0,1\}^{m}$ be a function computable by a circuit with
unbounded fan-in, arbitrary gates, $w$ wires and depth $d$. With
a very simple argument we show that the $m$-query problem corresponding
to $f$ has data structures with space $s=n+r$ and time $(w/r)^{d}$,
for any $r$. As a consequence, in the setting where $s$ is close
to $m$ a slight improvement on the state of existing data-structure
lower bounds would solve long-standing problems in circuit complexity.
We also use this connection to obtain a data structure for error-correcting
codes which nearly matches the 2007 lower bound by Gal and Miltersen.
This data structure can also be made dynamic. Finally we give a problem
that requires at least $3$ bit probes for $m=n^{O(1)}$ and even
$s=m/2-1$.
An independent work by Dvir, Golovnev, and Weinstein (2018) gives an incomparable connection between data-structure lower bounds and matrix rigidity.Tue, 13 Nov 2018 20:06:58 +0200https://eccc.weizmann.ac.il/report/2018/186#revision1
Paper TR18-186
| Lower bounds for data structures with space close to maximum imply circuit lower bounds |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2018/186Let $f:\{0,1\}^{n}\to\{0,1\}^{m}$ be a function computable by a circuit with
unbounded fan-in, arbitrary gates, $w$ wires and depth $d$. With
a very simple argument we show that the $m$-query problem corresponding
to $f$ has data structures with space $s=n+r$ and time $(w/r)^{d}$,
for any $r$. As a consequence, in the setting where $s$ is close
to $m$ a slight improvement on the state of existing data-structure
lower bounds would solve long-standing problems in circuit complexity.
We also use this connection to obtain a data structure for error-correcting
codes which nearly matches the 2007 lower bound by Gal and Miltersen.
This data structure can also be made dynamic. Finally we give a problem
that requires at least $3$ bit probes for $m=n^{O(1)}$ and even
$s=m/2-1$.
Tue, 06 Nov 2018 19:08:29 +0200https://eccc.weizmann.ac.il/report/2018/186