6 papers · 1 filter
On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths
Yu Cheng, Tianle Jiang, Pachara Sawettamalya +1
We revisit several fundamental graph problems in the deterministic two-party communication model. Our main contributions include: (1) a new -bit protocol fo…
A (Very) Nearly Optimal Sketch for -Edge Connectivity Certificates
Pachara Sawettamalya, Huacheng Yu
In this note, we present a simple algorithm for computing a \emph{-connectivity certificate} in dynamic graph streams. Our algorithm uses $O(n \log^2 n \cdot \max\{k, \log n \lo…
Optimally detecting uniformly-distributed heavy hitters in data streams
Santhoshini Velusamy, Huacheng Yu
Given a stream of items from a Universe of size poly, and a parameter , an item is said to be an heavy hitter if its frequency $…
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…
Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors
Elena Gribelyuk, Pachara Sawettamalya, Hongxun Wu +1
Computing the approximate quantiles or ranks of a stream is a fundamental task in data monitoring. Given a stream of elements and a query , a relative-err…
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…