תמונה

Graham Cormode

University of Warwick, UK

 

ירצה על

Will lecture on

New Lower and Upper Bounds for quantile summary algorithms


 

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(sqrt(log(epsilon N))) factor.

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

Zoom link:  

https://us02web.zoom.us/j/83383478356