22 citations · 28 across the 4 of their papers we have counts for
6 papers · 1 filter
Approximate Near Neighbors for General Symmetric Norms
Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov +2
We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every , $d = n^{o(1…
Heavy hitters via cluster-preserving clustering
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen +1
In turnstile -heavy hitters, one maintains a high-dimensional subject to causing , where $i\i…
On the Convergence of the Hegselmann-Krause System
Arnab Bhattacharyya, Mark Braverman, Bernard Chazelle +1
We study convergence of the following discrete-time non-linear dynamical system: n agents are located in R^d and at every time step, each moves synchronously to the average locatio…
OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson, Huy L. Nguyen
An "oblivious subspace embedding (OSE)" given some parameters eps,d is a distribution D over matrices B in R^{m x n} such that for any linear subspace W in R^n with dim(W) = d it h…
Sparsity Lower Bounds for Dimensionality Reducing Maps
Jelani Nelson, Huy L. Nguyen
We give near-tight lower bounds for the sparsity required in several dimensionality reducing linear maps. First, consider the JL lemma which states that for any set of n vectors in…
Sublinear Time Algorithms for Earth Mover's Distance
Khanh Do Ba, Huy L Nguyen, Huy N Nguyen +1
We study the problem of estimating the Earth Mover's Distance (EMD) between probability distributions when given access only to samples. We give closeness testers and additive-erro…