Title: New Lower and Upper Bounds for Quantile Summary Algorithms

Abstract: 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 Vesely, Justin Thaler, Edo Liberty and Zohar Karnin.
--