7 papers
Gap-Majority Lemmas in Communication Complexity
Pachara Sawettamalya, Huacheng Yu
We prove an information-theoretically optimal \emph{gap-majority lemma} in the two-player randomized communication model. For a base function , its $n…
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…
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…
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…
Strong XOR Lemma for Information Complexity
Pachara Sawettamalya, Huacheng Yu
For any -valued function , its \emph{-folded XOR} is the function where . Given a…
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…