Static data structure lower bounds imply rigidity

DOI10.1145/3313276.3316348zbMath1433.68102arXiv1811.02725OpenAlexW2963271334MaRDI QIDQ5212837

Zeev Dvir, Omri Weinstein, Alexander Golovnev

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

rigiditydata structurescodescircuit lower bound

Mathematics Subject Classification ID

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

Related Items

Polynomial Data Structure Lower Bounds in the Group Model, The function-inversion problem: barriers and opportunities, Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems, Lower bounds for matrix factorization, Lower bounds for matrix factorization, Efficient Construction of Rigid Matrices Using an NP Oracle, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization