9 citations · 13 across the 3 of their papers we have counts for
4 papers · 1 filter
Kernel Density Estimation through Density Constrained Near Neighbor Search
Moses Charikar, Michael Kapralov, Navid Nouri +1
In this paper we revisit the kernel density estimation problem: given a kernel and a dataset of points in high dimensional Euclidean space, prepare a data structure t…
Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
Arnold Filtser, Michael Kapralov, Navid Nouri
Graph sketching is a powerful technique introduced by the seminal work of Ahn, Guha and McGregor'12 on connectivity in dynamic graph streams that has enjoyed considerable attention…
Faster Spectral Sparsification in Dynamic Streams
Michael Kapralov, Aida Mousavifar, Cameron Musco +2
Graph sketching has emerged as a powerful technique for processing massive graphs that change over time (i.e., are presented as a dynamic stream of edge updates) over the past few…
Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space
Michael Kapralov, Navid Nouri, Aaron Sidford +1
In this paper we consider the problem of computing spectral approximations to graphs in the single pass dynamic streaming model. We provide a linear sketching based solution that g…