9 citations · 13 across the 3 of their papers we have counts for
5 papers
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…
Scaling up Kernel Ridge Regression via Locality Sensitive Hashing
Michael Kapralov, Navid Nouri, Ilya Razenshteyn +2
Random binning features, introduced in the seminal paper of Rahimi and Recht (2007), are an efficient method for approximating a kernel matrix using locality sensitive hashing. Ran…
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…