Colloquium on "New Lower and Upper Bounds for quantile summary algorithms"
given by Graham Cormode (University of Warwick). The seminar will take
place at 14:00 CET (local time in central Europe), and will be followed by
a discussion session. We would like to invite you to take part in the event
including the networking session. This new event aims to integrate the
European algorithmic community and keep it connected during the times of
the pandemic. The meeting will be held using Airmeet platform and to attend
please go to https://www.airmeet.com/e/43972b80-22ce-11eb-9abe-0fd8493f0346.
You can find more information about the talk on IGAFIT web page:
http://igafit.mimuw.edu.pl/?page_id=483786.
We invite you to take part in the event. Please advertise broadly and bring
your students/postdocs as well.
The details of the talk are given below.
November 12, 2020, 14:00 CET
Graham Cormode (University of Warwick)
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/epsilon)^3/2) factor.
This covers joint work with Pavel Vesely, Justin Thaler, Edo Liberty and
Zohar Karnin.
Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Adi Rosén
Eva Rotenberg
Piotr Sankowski
Christian Sohler
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
