6 papers · 1 filter
Sampling in Distributed Data Streams with Applications to Adversarial Robustness
Honghao Lin, Zhao Song, David P. Woodruff +2
In the distributed monitoring model, a data stream over a universe of size is distributed over servers, who must continuously provide certain statistics of the overall data…
Sublinear Time Quantum Sensitivity Sampling
Zhao Song, David P. Woodruff, Lichen Zhang
We present a unified framework for quantum sensitivity sampling, extending the advantages of quantum computing to a broad class of classical approximation problems. Our unified fra…
On Fine-Grained Distinct Element Estimation
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee +3
We study the problem of distributed distinct element estimation, where servers each receive a subset of a universe and aim to compute a -approximation to…
On Differential Privacy for Adaptively Solving Search Problems via Sketching
Shiyuan Feng, Ying Feng, George Z. Li +3
Recently differential privacy has been used for a number of streaming, data structure, and dynamic graph problems as a means of hiding the internal randomness of the data structure…
Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff +1
We show that both clustering and subspace embeddings can be performed in the streaming model with the same asymptotic efficiency as in the central/offline setting. For -clu…
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
We introduce a novel technique for ``lifting'' dimension lower bounds for linear sketches in the real-valued setting to dimension lower bounds for linear sketches with polynomially…