Jelani Nelson

activity

20082023

most citedOptimal approximate matrix product in terms of stable rank

65 citations · 262 across the 38 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

cs.DS2020

An Improved Sketching Algorithm for Edit Distance

Ce Jin, Jelani Nelson, Kewen Wu

We provide improved upper bounds for the simultaneous sketching complexity of edit distance. Consider two parties, Alice with input $x \in Σ^{n}$ and Bob with input $y \in Σ^{n}$ , that sha…

cs.DS2020★ 1 cited

On Adaptive Distance Estimation

Yeshwanth Cherapanamjeri, Jelani Nelson

We provide a static data structure for distance estimation which supports {\it adaptive} queries. Concretely, given a dataset $X = {x_{i}}_{i = 1}^{n}$ of $n$ points in $\mathbb{R}^d…

cs.DS2020★ 1 cited

Optimal bounds for approximate counting

Jelani Nelson, Huacheng Yu

Storing a counter incremented $N$ times would naively consume $O (lo g N)$ bits of memory. In 1978 Morris described the very first streaming algorithm: the "Morris Counter". His alg…