82 citations · 187 across the 27 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016★ 2 cited
How to Fake Multiply by a Gaussian Matrix
Michael Kapralov, Vamsi K. Potluru, David P. Woodruff
Have you ever wanted to multiply an matrix , with , on the left by an matrix of i.i.d. Gaussian random variables, but could not aff…
cs.DS2016★ 3 cited
Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time
Michael Kapralov
We consider the problem of computing a -sparse approximation to the Fourier transform of a length signal. Our main result is a randomized algorithm for computing such an app…
cs.DC2016★ 10 cited
Subgraph Counting: Color Coding Beyond Trees
Venkatesan T. Chakaravarthy, Michael Kapralov, Prakash Murali +4
The problem of counting occurrences of query graphs in a large data graph, known as subgraph counting, is fundamental to several domains such as genomics and social network analysi…