Author

G. Blelloch

h-index 60 View on Semantic Scholar

We have 2 of 332 papers

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Aug 2026

Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space

We show how to implement a dynamic array $A[1, n]$ with symbols from a fixed alphabet $\Sigma$, while supporting $O(1)$-time queries and updates, and using a total space of $$ \log \binom{|\Sigma|}{m} + \left(1 + O\left(\frac{\log \log n}{\log n}\right)\right) \cdot \left(\sum_{\sigma \in \Sigma} f_\sigma \log (n / f_\...

G. Blelloch, Yang Hu, William Kuszmaul et al. · 2 citations

Preprint Aug 2026

Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries

A dynamic dictionary is constructed that supports operations in $O(\log\varepsilon^{-1}/\log\log\varepsilon^{-1})$ expected amortized time and uses bits of space, and proves a matching lower bound, showing that the time-space tradeoff is optimal even in the \emph{static} case.

G. Blelloch, Yang Hu, William Kuszmaul et al. · 1 citation