Algorithms and Complexity Seminar
Sketching and Streaming Entropy via Approximation Theory
Jelani Nelson (MIT)
I will present near-optimal sketching and streaming algorithms for
estimating Shannon entropy in the most general streaming model, with
arbitrary insertions and deletions. This improves upon prior results
that obtain suboptimal space bounds in the general model, and
near-optimal bounds in the insertion-only model without sketching.
Our high-level approach is simple: we give algorithms to estimate
Renyi and Tsallis entropy, and use them to extrapolate an estimate of
Shannon entropy. The accuracy of our estimates is proven using
approximation theory arguments and extremal properties of Chebyshev
polynomials. Our work also yields the best-known and near-optimal
additive approximations for entropy, and hence also for conditional
entropy and mutual information.
This talk is based upon joint work with Nicholas J. A. Harvey (MSR /
UWaterloo) and Krzysztof Onak (MIT) and will appear at FOCS 2008.