2 citations · 3 across the 2 of their papers we have counts for
5 papers · 1 filter
The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis
William Kuszmaul, Qi Qi
Azuma's inequality is a tool for proving concentration bounds on random variables. The inequality can be thought of as a natural generalization of additive Chernoff bounds. On the…
Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
Aaron Berger, William Kuszmaul, Adam Polak +2
We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of workers and a multiset of tasks,…
The One-Way Communication Complexity of Dynamic Time Warping Distance
Vladimir Braverman, Moses Charikar, William Kuszmaul +2
We resolve the randomized one-way communication complexity of Dynamic Time Warping (DTW) distance. We show that there is an efficient one-way communication protocol using $\widetil…
On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings
Moses Charikar, Ofir Geri, Michael P. Kim +1
Edit distance is a fundamental measure of distance between strings and has been widely studied in computer science. While the problem of estimating edit distance has been studied e…
Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables
William Kuszmaul
Cuckoo hashing guarantees constant-time lookups regardless of table density, making it a viable candidate for high-density tables. Cuckoo hashing insertions perform poorly at high…