Dingyu Wang

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

A Unified Construction of Streaming Sketches via the LÃ©vy-Khintchine Representation Theorem

Seth Pettie, Dingyu Wang

In the $d$ -dimensional turnstile streaming model, a frequency vector $x = (x (1), \dots, x (n)) \in (R^{d})^{n}$ is updated entry-wisely over a stream. We…

cs.DS2024

Multi-dimensional Approximate Counting

Dingyu Wang

The celebrated Morris counter uses $lo g_{2} lo g_{2} n + O (lo g_{2} I ¨ ^{- 1})$ bits to count up to $n$ with a relative error $I ¨ $ , where if $I^^»$ is the estimate of the current count $…

cs.DS2024

Optimal Protocols for 2-Party Contention Resolution

Dingyu Wang

\emph{Contention Resolution} is a fundamental symmetry-breaking problem in which $n$ devices must acquire temporary and exclusive access to some \emph{shared resource}, without the…