2011/12/21 by David P. Woodruff, Qin Zhang, Woodruff, David P. +1 · 5 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Stochastic Gradient Optimization Techniques #cs.DS
paper · pdf · doi:10.48550/arxiv.1112.5153
Added a formal embedding argument in Section 3.2.2. This embedding argument required some other changes in Section 3, causing us to relax the definition of k-GAP-MAJ to k-APPROX-SUM, which is a similar problem. We still use the original k-GAP_MAJ in Section 6.1. Section 4 also now has missing details regarding the predictor
openalex publication_date 2011/12/21 · arxiv created 2013/06/12 · arxiv updated 2013/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We resolve several fundamental questions in the area of distributed functional monitoring, initiated by Cormode, Muthukrishnan, and Yi (SODA, 2008). In this model there are k sites each tracking their input and communicating with a central coordinator that continuously maintain an approximate output to a function f computed over the union of the inputs. The goal is to minimize the communication. We show the randomized communication complexity of estimating the number of distinct elements up to a 1+\eps factor is Ω(k/\eps2), improving the previous Ω(k + 1/\eps2) bound and matching known upper bounds up to a logarithmic factor. For the p-th frequency moment Fp, p > 1, we improve the previous Ω(k + 1/\eps2) communication bound to Ω(kp-1/\eps2). We obtain similar improvements for heavy hitters, empirical entropy, and other problems. We also show that we can estimate Fp, for any p > 1, using O(kp-1\poly(\eps-1)) communication. This greatly improves upon the previous O(k2p+1N1-2/p \poly(\eps-1)) bound of Cormode, Muthukrishnan, and Yi for general p, and their O(k2/\eps + k1.5/\eps3) bound for p = 2. For p = 2, our bound resolves their main open question. Our lower bounds are based on new direct sum theorems for approximate majority, and yield significant improvements to problems in the data stream model, improving the bound for estimating Fp, p > 2, in t passes from Ω(n1-2/p/(\eps2/p t)) to Ω(n1-2/p/(\eps4/p t)), giving the first bound for estimating F0 in t passes of Ω(1/(\eps2 t)) bits of space that does not use the gap-hamming problem.