[Proof Complexity] Seminar Friday Sep 17 at 14:00 CEST with Kuldeep Meel: Estimating the size of unions of sets in streaming model

[Jakob Nordström]

Dear all,

This coming Friday September 17 at 14:00 we are having a MIAO video seminar with Kuldeep S. Meel from the National University of Singapore titled "Estimating the size of unions of sets in streaming model". See below for the abstract.

We will meet virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://www.youtube.com/channel/UCN0G2Wfl9-sAKrVLVza7z4A for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a 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 an overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming video seminars can be found at http://www.jakobnordstrom.se/videoseminars/ . If you do not wish to receive these announcements, or receive several copies of them, please send a message to jakob.nordstrom at cs.lth.se.

Best regards,
Jakob Nordström

**********

Friday Sep 17 at 14:00 CEST
Estimating the size of unions of sets in streaming model
(Kuldeep S. Meel, National University of Singapore)

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.)


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se