6 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…
Minimum -- Cuts with Fewer Cut Queries
Yonggang Jiang, Danupon Nanongkai, Pachara Sawettamalya
We study the problem of computing a minimum -- cut in an unweighted, undirected graph via \emph{cut queries}. In this model, the input graph is accessed through an oracle tha…
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…
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…
Strong XOR Lemma for Information Complexity
Pachara Sawettamalya, Huacheng Yu
For any -valued function , its \emph{-folded XOR} is the function where . Given a…