22 citations · 27 across the 3 of their papers we have counts for
4 papers
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…