Simulation beats Richness: New Data-Structure Lower Bounds
summary
Proves average-case lower bounds for Boolean matrix–vector problems by reducing data-structure probes to an asymmetric communication game and a lifting theorem. For uMv and orthogonal-count problems any randomized cell-probe scheme that makes fewer than ε·n probes has advantage at most 2^{-ε n}. Matches an upper bound of about n^2/(W log S) probes via block precomputation, and the reduction extracts a parity decision tree for the outer function using an inner-product gadget. The simulation gives TW vs T log S tradeoffs.
AI-written summary · about