pdf icon
Volume 15 (2019) Article 18 pp. 1-9
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds
Received: February 15, 2019
Revised: October 4, 2019
Published: December 18, 2019
Download article from ToC site:
[PDF (204K)]    [PS (775K)]    [PS.GZ (224K)]
[Source ZIP]
Keywords: data structure, lower bound, circuit, arbitrary gates, wires, error-correcting codes
ACM Classification: F.2.3
AMS Classification: 68Q17

Abstract: [Plain Text Version]

$ \newcommand{\zo}{\{0, 1\}} $

Let $f:\zo^{n}\to\zo^{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 Gál 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.