MIAO video seminar: Estimating the size of unions of sets in streaming model
Title: Estimating the size of unions of sets in streaming model
Speaker: Kuldeep S. Meel, National University of Singapore
Host: Jacob Nordström, Department of Computer Science, Lund University Joint with
Where: Online - link by registration
Feeling tired of complicated theorems with complicated proofs? Fret not; this week will be different: A simple theorem with a simpler proof for a general problem. I will make a case for our PODS-21 paper to be the simplest paper ever accepted at PODS.
A set is Delphic if it supports efficient membership, sampling, and counting calls. The notion of Delphic sets captures several well-known problems, such as Klee's measure, distinct elements, and model counting of DNF formulas. We will discuss estimation of the size of the union of Delphic sets wherein each set is implicitly (and succinctly) represented, and comes in a streaming fashion.
The primary contribution of our work is a simple, elegant, and efficient sampling-based algorithm for the estimation of the union in the streaming setting. Our algorithm has worst case space complexity and update time that is logarithmic in the size of the universe and stream size. Consequently, our algorithm provides the first algorithm with a linear dependence on d for Klee's measure problem in streaming setting for d>1, thereby settling the open problem of Woodruff and Tirthpura (PODS-12). The Klee's measure problem corresponds to computation of volume of multi-dimension axis-aligned rectangles, i.e., every d-dimension axis-aligned rectangle can be defined as [a_1,b_1] x [a_2,b_2] x … x [a_d, b_d].
(Joint work with N.V. Vinodchandran and Sourav Chakraborty.)
Please register at lth.se/digitalth/events/register-miao-09-17 in order to get an access link to the zoom platform.
The MIAO video seminars are arranged by the Mathematical Insights into Algorithms for Optimization (MIAO) research group at the University of Copenhagen and Lund University. Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break an optional ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results. For listeners who are particularly interested, there is then an opportunity to return for a second part where we get into more technical details.