3 papers
cs.DS2024
Optimal Protocols for 2-Party Contention Resolution
Dingyu Wang
\emph{Contention Resolution} is a fundamental symmetry-breaking problem in which 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 which is updated through a stream of pairs where and $k\in…
cs.DS2022
Simpler and Better Cardinality Estimators for HyperLogLog and PCSA
Seth Pettie, Dingyu Wang
\emph{Cardinality Estimation} (aka \emph{Distinct Elements}) is a classic problem in sketching with many industrial applications. Although sketching \emph{algorithms} are fairly si…