An optimal algorithm for the distinct elements problem DM Kane, J Nelson, DP Woodruff Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on …, 2010 | 297 | 2010 |

OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings J Nelson, HL Nguyên 2013 ieee 54th annual symposium on foundations of computer science, 117-126, 2013 | 287 | 2013 |

Sparser johnson-lindenstrauss transforms DM Kane, J Nelson Journal of the ACM (JACM) 61 (1), 1-23, 2014 | 258 | 2014 |

Cache-oblivious streaming B-trees MA Bender, M Farach-Colton, JT Fineman, YR Fogel, BC Kuszmaul, ... Proceedings of the nineteenth annual ACM symposium on Parallel algorithms …, 2007 | 192 | 2007 |

On the exact space complexity of sketching and streaming small norms DM Kane, J Nelson, DP Woodruff Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete …, 2010 | 147 | 2010 |

Sketching and streaming entropy via approximation theory NJA Harvey, J Nelson, K Onak 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 489-498, 2008 | 112 | 2008 |

Optimal approximate matrix product in terms of stable rank MB Cohen, J Nelson, DP Woodruff arXiv preprint arXiv:1507.02268, 2015 | 108 | 2015 |

Heavy hitters and the structure of local privacy M Bun, J Nelson, U Stemmer ACM Transactions on Algorithms (TALG) 15 (4), 1-40, 2019 | 103 | 2019 |

Toward a unified theory of sparse dimensionality reduction in euclidean space J Bourgain, S Dirksen, J Nelson Geometric and Functional Analysis 25 (4), 1009-1088, 2015 | 101 | 2015 |

Bounded independence fools degree-2 threshold functions I Diakonikolas, DM Kane, J Nelson 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 11-20, 2010 | 92 | 2010 |

Optimality of the Johnson-Lindenstrauss lemma KG Larsen, J Nelson 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017 | 82 | 2017 |

Fast moment estimation in data streams in optimal space DM Kane, J Nelson, E Porat, DP Woodruff Proceedings of the forty-third annual ACM symposium on Theory of computing …, 2011 | 82 | 2011 |

Heavy hitters via cluster-preserving clustering KG Larsen, J Nelson, HL Nguyên, M Thorup 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 61-70, 2016 | 64 | 2016 |

The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction KG Larsen, J Nelson arXiv preprint arXiv:1411.2404, 2014 | 59 | 2014 |

Almost optimal explicit Johnson-Lindenstrauss families D Kane, R Meka, J Nelson Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2011 | 58 | 2011 |

A derandomized sparse Johnson-Lindenstrauss transform DM Kane, J Nelson arXiv preprint arXiv:1006.3585, 2010 | 57 | 2010 |

New constructions of RIP matrices with fast multiplication and fewer rows J Nelson, E Price, M Wootters Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete …, 2014 | 51 | 2014 |

BPTree: An ℓ_{2} Heavy Hitters Algorithm Using Constant MemoryV Braverman, SR Chestnut, N Ivkin, J Nelson, Z Wang, DP Woodruff Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of …, 2017 | 49 | 2017 |

Sparsity lower bounds for dimensionality reducing maps J Nelson, HL NguyÅn Proceedings of the forty-fifth annual ACM symposium on Theory of computing …, 2013 | 48 | 2013 |

Sorting and selection with imprecise comparisons M Ajtai, V Feldman, A Hassidim, J Nelson International Colloquium on Automata, Languages, and Programming, 37-48, 2009 | 39 | 2009 |