__
Revision #1 to TR18-186 | 13th November 2018 20:06
__
#### Lower bounds for data structures with space close to maximum imply circuit lower bounds

**Abstract:**
Let $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.

**Changes to previous version:**
Added a discussion of Dvir, Golovnev, and Weinstein (2018).

__
TR18-186 | 6th November 2018 19:07
__

#### Lower bounds for data structures with space close to maximum imply circuit lower bounds

**Abstract:**
Let $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$.