Static data structure lower bounds imply rigidity

DOI10.1145/3313276.3316348MaRDI QIDQ5212837zbMATH OpenOpenAlexFDO

Authors Zeev Dvir, Alexander Golovnev, O. Weinstein

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.02725

zbMATH Keywords

circuit lower boundcodesdata structuresrigidity

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We 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 $tgeqomega(lo{g}^{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 ($$) 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 ($tgeq{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.

Recommendations

• scientific article; zbMATH DE number 3852432
• On the algorithmic complexity of static structures
• Data Structures Lower Bounds and Popular Conjectures
• Lower bounds for data structures with space close to maximum imply circuit lower bounds
• Searching rigid data structures
• Lower bounds for dynamic data structures on algebraic RAMs
• Locally finite properties of data structures and their computation
• scientific article; zbMATH DE number 7650383
• Computer Aided Verification

Cited in

(12)

• Lower bounds for matrix factorization
• Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
• The function-inversion problem: barriers and opportunities
• scientific article; zbMATH DE number 3852432 (Why is no real title available?)
• Polynomial data structure lower bounds in the group model
• Lower bounds for matrix factorization
• Lower bounds for data structures with space close to maximum imply circuit lower bounds
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
• Efficient construction of rigid matrices using an NP oracle
• Block rigidity: strong multiplayer parallel repetition implies super-linear lower bounds for Turing machines
• Kronecker products, low-depth circuits, and matrix rigidity

This page was built for publication: Static data structure lower bounds imply rigidity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212837)