2026/08/06 by Guy E. Blelloch, Yang Hu, William Kuszmaul +2
Computer Science · #cs.DS
39 pages. In FOCS 2026
arxiv created 2026/08/06 · arxiv updated 2026/08/07
We show how to implement a dynamic array A[1, n] with symbols from a fixed alphabet Σ, while supporting O(1)-time queries and updates, and using a total space of log \binom|Σ|m + (1 + O((log log n)/(log n))) ⋅ (∑σ∈ Σ fσlog (n / fσ)) + n / polylog n bits, where fσ denotes the frequency of each symbol σ∈ Σ and m denotes the number of distinct symbols with non-zero frequencies. This resolves a long-standing open question as to whether one can achieve space bounds close to that of arithmetic coding, while supporting O(1)-time operations, whenever the entropy is at least n/polylog n. We also prove a nearly matching space lower bound: up to a factor of O(log log n), the entropy-dependent multiplicative overhead of our construction is optimal among O(1)-time solutions when |Σ|=O(√ n) and the entropy ∑σ∈ Σ fσlog (n / fσ) lies between n/logO(1)n and (1/100)nlog n. Finally, we present several applications of our results, resolving two open problems having to do with space-efficient dictionaries and filters.