Dingyu Wang

collaborators

4 papers

cs.DS2024

Multi-dimensional Approximate Counting

Dingyu Wang

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

cs.DS2024

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

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…

cs.DS2023

Probabilistic Counting in Generalized Turnstile Models

Dingyu Wang

Traditionally in the turnstile model of data streams, there is a state vector $x = (x_{1}, x_{2}, \dots, x_{n})$ which is updated through a stream of pairs $(i, k)$ where $i \in [n]$ and $k\in…