Theory of Computing
-------------------
Title : Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds
Authors : Emanuele Viola
Volume : 15
Number : 18
Pages : 1-9
URL : https://theoryofcomputing.org/articles/v015a018
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$.
Independent work by Dvir, Golovnev, and Weinstein (2018) and by
Corrigan-Gibbs and Kogan (2018) give incomparable connections between
data-structure and other types of lower bounds.