Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication
summary
Proves a concrete tradeoff in the succinct cell‑probe model: using an information‑theoretic encoding of a hard distribution (one 1 per block) and careful probe accounting, the extra storage R and query probes T satisfy R·T = Ω(n^3), so if R = o(n^{3/2}) then T = ω(n^{3/2}); as a corollary, R < n forces probing almost every input bit. Also gives a matching randomized systematic succinct structure with R,T = Õ(n^{3/2}) using sparse‑submatrix listings and sampling.
AI-written summary · about