Seminars

View all Seminars  |  Download ICal for this event

Distinct Elements in Streams and the Klees Measure Problem

Series: Bangalore Theory Seminars

Speaker: Sourav Chakraborty, ISI Kolkata

Date/Time: Apr 03 16:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract:
We will present a very simple streaming algorithm on F_0 esimation that also caught the eye of Donald E. Knuth. <br /><br />

This simple algorithm comes out of the first ever &nbspefficient  streaming algorithm (from PODS 21) for the Klees Measure problem, which was a big open problem in the world of streaming for many years. <br /><br />

This work is based on joint works with N. V. Vinodchandran, and Kuldeep S. Meel across multiple articles, notable the following: <br /><br />

Estimating the Size of Union of Sets in Streaming Models. PODS 2021 <br /><br />
Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size. PODS 2022 <br /><br />
Distinct Elements in Streams: An Algorithm for the (Text) Book. ESA 2022<br /><br />
<br /><br />

Microsoft team link:<br /><br />
<br /><br />
Link /><br />
<br /><br />
<br /><br />
We are grateful to the Kirani family for generously supporting the theory seminar series<br /><br />
<br /><br />
Hosts: Rameesh Paul, KVN Sreenivas, Rahul Madhavan, Debajyoti Kar