DIMACS Theoretical Computer Science Seminar


Title: Large Frequency Moments and Universal Sketches

Speaker: Vladimir Braverman, Johns Hopkins University

Date: Wednesday, October 14, 2015 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ


Abstract:

We consider the problem of approximating frequency moments in the streaming model. Given a stream D = {p_1,p_2,...,p_m} of numbers from {1,...,n}, a frequency of i is defined as f_i = |{j: p_j = i}|. The k-th frequency moment of D is defined as F_k = \sum_{i=1}^n f_i^k. In their celebrated paper, Alon, Matias, and Szegedy (STOC 1996) introduced the problem of computing a (1 +/- epsilon)-approximation of F_k with sublinear memory. We give upper bound of O(n^{1-2/k}) bits that matches, up to a constant factor, the lower bound of Woodruff and Zhang (STOC 12) for constant epsilon and k > 3 (joint work with Jonathan Katzman, Charles Seidell and Gregory Vorsanger, APPROX 14). If time permits, we will present some recent results on universal sketches (joint works with Alan Roytman and Rafail Ostrovsky, RANDOM 15, and Stephen Chestnut, RANDOM 15), and k-median clustering on sliding windows (joint work Harry Lang, Keith Levin and Morteza Monemizadeh, SODA 16, FSTTCS 16).

See: https://dragon.rutgers.edu/~mk1029/theoryseminarF15.html