14 papers · 1 filter
The Adversarial Robustness of Sketching and Streaming Algorithms
David P. Woodruff, Samson Zhou
Sketching and streaming algorithms are vital for handling massive datasets. While classical methods guarantee correctness on fixed inputs, they often fail with adaptive inputs, whe…
Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While recent work achieved a robust…
Distributed Algorithms for Euclidean Clustering
Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff +1
We study the problem of constructing -coresets for Euclidean -clustering in the distributed setting, where data points are partitioned across sites.…
Learning-Augmented Moment Estimation on Time-Decay Models
Soham Nagawanshi, Shalini Panthangi, Chen Wang +2
Motivated by the prevalence and success of machine learning, a line of recent work has studied learning-augmented algorithms in the streaming model. These results have shown that f…
Consistent Low-Rank Approximation
David P. Woodruff, Samson Zhou
We introduce and study the problem of consistent low-rank approximation, in which rows of an input matrix arrive sequentially and the goal is…
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…
Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
David P. Woodruff, Samson Zhou
In the adversarial streaming model, the input is a sequence of adaptive updates that defines an underlying dataset and the goal is to approximate, collect, or compute some statisti…
A Strong Separation for Adversarially Robust Estimation for Linear Sketches
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
The majority of streaming problems are defined and analyzed in a static setting, where the data stream is any worst-case sequence of insertions and deletions that is fixed in advan…
Fast White-Box Adversarial Streaming Without a Random Oracle
Ying Feng, Aayush Jain, David P. Woodruff
Recently, the question of adversarially robust streaming, where the stream is allowed to depend on the randomness of the streaming algorithm, has gained a lot of attention. In this…