Graham Cormode (University of Warwick and Facebook) (webinar)
18 February 2022 @ 12:00 - 13:00
- Past event
“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.