Static Data Structure Lower Bounds Imply Rigidity
summary
Shows that linear static data-structure hardness translates to matrix rigidity: if an n-input linear problem resists S = n(1+ε) space and small probe time T then the problem’s matrix contains a rigid submatrix with rank or sparsity parameters improving prior bounds. Uses concrete decompositions (sparse plus low-rank), proves equivalences between inner/outer dimension and data-structure complexity, constructs explicit rectangular-to-square reductions, and gives quantitative statements about εn sparsity and probe-time tradeoffs.
AI-written summary · about