Jelani Nelson

Publication Activity (10 Years)

Years Active: 2005-2024
Publications (10 Years): 74

Top Venues

CoRR

STOC

FOCS

NeurIPS

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Yeshwanth Cherapanamjeri, Jelani Nelson
Terminal Embeddings in Sublinear Time. TheoretiCS 3 (2024)
Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar, Samson Zhou
Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages. CoRR (2024)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries. COLT (2024)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries. CoRR (2024)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries. IACR Cryptol. ePrint Arch. 2024 (2024)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization. STOC (2023)
Badih Ghazi, Ravi Kumar, Jelani Nelson, Pasin Manurangsi
Private Counting of Distinct and k-Occurring Items in Time Windows. ITCS (2023)
Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar
Fast Optimal Locally Private Mean Estimation via Random Projections. NeurIPS (2023)
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou
Differentially Private Aggregation via Imperfect Shuffling. CoRR (2023)
Edith Cohen, Jelani Nelson, Tamás Sarlós, Uri Stemmer
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs. AAAI (2023)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
Generalized Private Selection and Testing with High Confidence. ITCS (2023)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
Hot PATE: Private Aggregation of Distributions for Diverse Task. CoRR (2023)
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou
Differentially Private Aggregation via Imperfect Shuffling. ITC (2023)
Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. SODA (2023)
Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn
Sparse Dimensionality Reduction Revisited. CoRR (2023)
Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar
Fast Optimal Locally Private Mean Estimation via Random Projections. CoRR (2023)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization. CoRR (2022)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
Generalized Private Selection and Testing with High Confidence. CoRR (2022)
Yeshwanth Cherapanamjeri, Jelani Nelson
Uniform approximations for Randomized Hadamard Transforms with applications. STOC (2022)
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson
Private Counting of Distinct and k-Occurring Items in Time Windows. CoRR (2022)
Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
Estimation of Entropy in Constant Space with Improved Sample Complexity. CoRR (2022)
Jelani Nelson, Huacheng Yu
Optimal Bounds for Approximate Counting. PODS (2022)
Vitaly Feldman, Jelani Nelson, Huy Le Nguyen, Kunal Talwar
Private Frequency Estimation via Projective Geometry. CoRR (2022)
Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
Estimation of Entropy in Constant Space with Improved Sample Complexity. NeurIPS (2022)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, Uri Stemmer
On the Robustness of CountSketch to Adaptive Inputs. CoRR (2022)
Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar
Private frequency estimation via projective geometry. ICML (2022)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, Uri Stemmer
On the Robustness of CountSketch to Adaptive Inputs. ICML (2022)
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. CoRR (2022)
Ishaq Aden-Ali, Yanjun Han, Jelani Nelson, Huacheng Yu
On the amortized complexity of approximate counting. CoRR (2022)
Nishanth Dikkala, Sankeerth Rao Karingula, Raghu Meka, Jelani Nelson, Rina Panigrahy, Xin Wang
Sketching based Representations for Robust Image Classification with Provable Guarantees. NeurIPS (2022)
Yeshwanth Cherapanamjeri, Jelani Nelson
Uniform Approximations for Randomized Hadamard Transforms with Applications. CoRR (2022)
Yeshwanth Cherapanamjeri, Jelani Nelson
Terminal Embeddings in Sublinear Time. FOCS (2022)
Edith Cohen, Jelani Nelson, Tamás Sarlós, Uri Stemmer
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs. CoRR (2022)
Shuchi Chawla, Jelani Nelson, Chris Umans, David P. Woodruff
Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020. CoRR (2021)
Yeshwanth Cherapanamjeri, Jelani Nelson
Terminal Embeddings in Sublinear Time. FOCS (2021)
Aydin Buluç, Tamara G. Kolda, Stefan M. Wild, Mihai Anitescu, Anthony DeGennaro, John Jakeman, Chandrika Kamath, Ramakrishnan Kannan, Miles E. Lopes, Per-Gunnar Martinsson, Kary Myers, Jelani Nelson, Juan M. Restrepo, C. Seshadhri, Draguna L. Vrabie, Brendt Wohlberg, Stephen J. Wright, Chao Yang, Peter Zwart
Randomized Algorithms for Scientific Computing (RASC). CoRR (2021)
Yeshwanth Cherapanamjeri, Jelani Nelson
Terminal Embeddings in Sublinear Time. CoRR (2021)
Ce Jin, Jelani Nelson, Kewen Wu
An Improved Sketching Algorithm for Edit Distance. STACS (2021)
Yeshwanth Cherapanamjeri, Jelani Nelson
On Adaptive Distance Estimation. NeurIPS (2020)
Yeshwanth Cherapanamjeri, Jelani Nelson
On Adaptive Distance Estimation. CoRR (2020)
Jelani Nelson, Huacheng Yu
Optimal bounds for approximate counting. CoRR (2020)
Ce Jin, Jelani Nelson, Kewen Wu
An Improved Sketching Bound for Edit Distance. CoRR (2020)
Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson
Margin-Based Generalization Lower Bounds for Boosted Classifiers. NeurIPS (2019)
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
Heavy hitters via cluster-preserving clustering. Commun. ACM 62 (8) (2019)
Shyam Narayanan, Jelani Nelson
Optimal terminal dimensionality reduction in Euclidean space. STOC (2019)
Jelani Nelson, Huacheng Yu
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. SODA (2019)
Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson
Margin-Based Generalization Lower Bounds for Boosted Classifiers. CoRR (2019)
Mark Bun, Jelani Nelson, Uri Stemmer
Heavy Hitters and the Structure of Local Privacy. ACM Trans. Algorithms 15 (4) (2019)
Jelani Nelson, Huacheng Yu
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. CoRR (2018)
Michael B. Cohen, T. S. Jayram, Jelani Nelson
Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. SOSA (2018)
Mark Bun, Jelani Nelson, Uri Stemmer
Heavy Hitters and the Structure of Local Privacy. PODS (2018)
Jelani Nelson, Huacheng Yu
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. Electron. Colloquium Comput. Complex. 25 (2018)
Shyam Narayanan, Jelani Nelson
Optimal terminal dimensionality reduction in Euclidean space. CoRR (2018)
Tom Morgan, Jelani Nelson
A Note on Reductions Between Compressed Sensing Guarantees. ISIT (2018)
Jian Ding, Jaroslaw Blasiok, Jelani Nelson
norms in data streams. CoRR (2017)
Jelani Nelson, Jakub Pachocki, Zhengyu Wang
Optimal lower bounds for universal relation, samplers, and finding duplicates. CoRR (2017)
Kasper Green Larsen, Jelani Nelson
Optimality of the Johnson-Lindenstrauss Lemma. FOCS (2017)
Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh
Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams. CoRR (2017)
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff
Heavy Hitters Algorithm Using Constant Memory. PODS (2017)
Jacob Teo Por Loong, Jelani Nelson, Huacheng Yu
Fillable arrays with constant time operations and a single bit of redundancy. CoRR (2017)
Mark Bun, Jelani Nelson, Uri Stemmer
Heavy Hitters and the Structure of Local Privacy. CoRR (2017)
Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh
Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. FOCS (2017)
Jaroslaw Blasiok, Jian Ding, Jelani Nelson
Continuous Monitoring of l_p Norms in Data Streams. APPROX-RANDOM (2017)
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff
heavy hitters algorithm using constant memory. CoRR (2016)
Jaroslaw Blasiok, Jelani Nelson
An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm. ICALP (2016)
Kasper Green Larsen, Jelani Nelson
The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. ICALP (2016)
Jelani Nelson
Chaining introduction with some computer science applications. Bull. EATCS 120 (2016)
Michael B. Cohen, Jelani Nelson, David P. Woodruff
Optimal Approximate Matrix Product in Terms of Stable Rank. ICALP (2016)
Jaroslaw Blasiok, Jelani Nelson
An improved analysis of the ER-SpUD dictionary learning algorithm. CoRR (2016)
Kasper Green Larsen, Jelani Nelson
Optimality of the Johnson-Lindenstrauss Lemma. CoRR (2016)
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
Heavy hitters via cluster-preserving clustering. CoRR (2016)
Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
Sorting and Selection with Imprecise Comparisons. ACM Trans. Algorithms 12 (2) (2016)
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
Heavy Hitters via Cluster-Preserving Clustering. FOCS (2016)
Tom Morgan, Jelani Nelson
A note on reductions between compressed sensing guarantees. CoRR (2016)
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyên
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms. STOC (2015)
Jean Bourgain, Sjoerd Dirksen, Jelani Nelson
Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space. STOC (2015)
Michael B. Cohen, Jelani Nelson, David P. Woodruff
Optimal approximate matrix product in terms of stable rank. CoRR (2015)
Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
Sorting and Selection with Imprecise Comparisons. CoRR (2015)
Daniel M. Kane, Jelani Nelson
Sparser Johnson-Lindenstrauss Transforms. J. ACM 61 (1) (2014)
Kasper Green Larsen, Jelani Nelson
The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction. CoRR (2014)
Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen
Time lower bounds for nonadaptive turnstile streaming algorithms. CoRR (2014)
Jelani Nelson, Huy L. Nguyên
Lower Bounds for Oblivious Subspace Embeddings. ICALP (1) (2014)
Jelani Nelson, Eric Price, Mary Wootters
New constructions of RIP matrices with fast multiplication and fewer rows. SODA (2014)
Jelani Nelson, Huy L. Nguyen
Sparsity lower bounds for dimensionality reducing maps. STOC (2013)
Jelani Nelson, Huy L. Nguyen
Lower bounds for oblivious subspace embeddings. CoRR (2013)
Jean Bourgain, Jelani Nelson
Toward a unified theory of sparse dimensionality reduction in Euclidean space. CoRR (2013)
Jelani Nelson, Huy L. Nguyen
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings. FOCS (2013)
Jelani Nelson, Huy L. Nguyen
OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings CoRR (2012)
Jelani Nelson
Sketching and streaming algorithms for processing massive data. XRDS 19 (1) (2012)
Jelani Nelson, Huy L. Nguyen
Sparsity Lower Bounds for Dimensionality Reducing Maps CoRR (2012)
Jelani Nelson, Huy L. Nguyên, David P. Woodruff
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation CoRR (2012)
Daniel M. Kane, Jelani Nelson
Sparser Johnson-Lindenstrauss transforms. SODA (2012)
Jelani Nelson, Huy L. Nguyên, David P. Woodruff
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. APPROX-RANDOM (2012)
Jelani Nelson, Eric Price, Mary Wootters
New constructions of RIP matrices with fast multiplication and fewer rows CoRR (2012)
Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff
Fast moment estimation in data streams in optimal space. STOC (2011)
Daniel M. Kane, Raghu Meka, Jelani Nelson
Almost Optimal Explicit Johnson-Lindenstrauss Families. APPROX-RANDOM (2011)
Daniel M. Kane, Jelani Nelson, David P. Woodruff
On the Exact Space Complexity of Sketching and Streaming Small Norms. SODA (2010)
Daniel M. Kane, Jelani Nelson
A Sparser Johnson-Lindenstrauss Transform CoRR (2010)
Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson
Bounded Independence Fools Degree-2 Threshold Functions. FOCS (2010)
Daniel M. Kane, Jelani Nelson, David P. Woodruff
An optimal algorithm for the distinct elements problem. PODS (2010)

Jelani Nelson.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Jelani Nelson