New lower and upper bounds for quantile summary algorithms, Nov. 2020. IGAFIT colloquium and Bar-Ilan University Colloquium.

Finding the median, or more generally quantiles, is a core problem in data analysis. The question has been heavily studied in streaming and related models of computation, for over four decades. In this talk I will present some recent advances:

- Lower bounds for approximating quantiles in the deterministic comparison model, for additive error, which show that the best known algorithm is in fact optimal

- Upper bounds for relative error epsilon-approximations of quantiles, which improves over previous results and exceed the best known lower bounds by only an O(log(1/e)3/2) factor.

This covers joint work with Pavel Veselư, Justin Thaler, Edo Liberty and Zohar Karnin.

[ bib | video ] Back

This file was generated by bibtex2html 1.92.