Speaker: |
Sourav Chakraborty (ISI Kolkata) |

Organiser: |
Ramprasad Saptharishi |

Date: |
Friday, 27 Jan 2023, 16:00 to 17:00 |

Venue: |
A201 |

(Scan to add to calendar)

We present a simple algorithm that estimates the size of the union, upto a (1 + \epsilon) factor, in space complexity and update time complexity O(log(M)^2/\epsilon^2).

Our algorithm provides the first algorithm with polynomial dependence on the dimension for Klee’s measure problem in streaming setting and independent of the stream size, thereby settling the open problem of Woodruff and Tirthpura (PODS-12).

This talk will be based on works with Kuldeep Meel and Vinodchandran (PODS21, PODS22 and ESA22).