Jelani Nelson

According to our database, Jelani Nelson authored at least 73 papers between 2005 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Terminal Embeddings in Sublinear Time.

Yeshwanth Cherapanamjeri, Jelani Nelson

TheoretiCS, 2024

Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries.

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer

IACR Cryptol. ePrint Arch., 2024

Sparse Dimensionality Reduction Revisited.

Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn

Proceedings of the Forty-first International Conference on Machine Learning, 2024

Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages.

Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar, Samson Zhou

Proceedings of the Forty-first International Conference on Machine Learning, 2024

On the Amortized Complexity of Approximate Counting.

Ishaq Aden-Ali, Yanjun Han, Jelani Nelson, Huacheng Yu

Proceedings of the Approximation, 2024

2023

Hot PATE: Private Aggregation of Distributions for Diverse Task.

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer

CoRR, 2023

Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization.

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds.

Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Fast Optimal Locally Private Mean Estimation via Random Projections.

Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Private Counting of Distinct and k-Occurring Items in Time Windows.

Badih Ghazi, Ravi Kumar, Jelani Nelson, Pasin Manurangsi

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Generalized Private Selection and Testing with High Confidence.

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Differentially Private Aggregation via Imperfect Shuffling.

Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou

Proceedings of the 4th Conference on Information-Theoretic Cryptography, 2023

Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs.

Edith Cohen, Jelani Nelson, Tamás Sarlós, Uri Stemmer

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds.

Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson

CoRR, 2022

Uniform approximations for Randomized Hadamard Transforms with applications.

Yeshwanth Cherapanamjeri, Jelani Nelson

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Optimal Bounds for Approximate Counting.

Jelani Nelson, Huacheng Yu

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Sketching based Representations for Robust Image Classification with Provable Guarantees.

Nishanth Dikkala, Sankeerth Rao Karingula, Raghu Meka, Jelani Nelson, Rina Panigrahy, Xin Wang

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Estimation of Entropy in Constant Space with Improved Sample Complexity.

Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Private frequency estimation via projective geometry.

Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar

Proceedings of the International Conference on Machine Learning, 2022

On the Robustness of CountSketch to Adaptive Inputs.

Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, Uri Stemmer

Proceedings of the International Conference on Machine Learning, 2022

2021

Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020.

Shuchi Chawla, Jelani Nelson, Chris Umans, David P. Woodruff

CoRR, 2021

Randomized Algorithms for Scientific Computing (RASC).

Aydin Buluç, Tamara G. Kolda, Stefan M. Wild, Mihai Anitescu, Anthony M. DeGennaro, John Jakeman, Chandrika Kamath, Ramakrishnan Kannan, Miles E. Lopes, Per-Gunnar Martinsson, Kary L. Myers, Jelani Nelson, Juan M. Restrepo, C. Seshadhri, Draguna L. Vrabie, Brendt Wohlberg, Stephen J. Wright, Chao Yang, Peter Zwart

CoRR, 2021

An Improved Sketching Algorithm for Edit Distance.

Ce Jin, Jelani Nelson, Kewen Wu

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

2020

An Improved Sketching Bound for Edit Distance.

Ce Jin, Jelani Nelson, Kewen Wu

CoRR, 2020

On Adaptive Distance Estimation.

Yeshwanth Cherapanamjeri, Jelani Nelson

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

2019

Heavy Hitters and the Structure of Local Privacy.

Mark Bun, Jelani Nelson, Uri Stemmer

ACM Trans. Algorithms, 2019

Heavy hitters via cluster-preserving clustering.

Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup

Commun. ACM, 2019

Optimal terminal dimensionality reduction in Euclidean space.

Shyam Narayanan, Jelani Nelson

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Margin-Based Generalization Lower Bounds for Boosted Classifiers.

Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation.

Jelani Nelson, Huacheng Yu

Electron. Colloquium Comput. Complex., 2018

Simple Analyses of the Sparse Johnson-Lindenstrauss Transform.

Michael B. Cohen, T. S. Jayram, Jelani Nelson

Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

A Note on Reductions Between Compressed Sensing Guarantees.

Tom Morgan, Jelani Nelson

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

2017

Fillable arrays with constant time operations and a single bit of redundancy.

Jacob Teo Por Loong, Jelani Nelson, Huacheng Yu

CoRR, 2017

Optimal lower bounds for universal relation, samplers, and finding duplicates.

Jelani Nelson, Jakub Pachocki, Zhengyu Wang

CoRR, 2017

Continuous monitoring of 𝓁_p norms in data streams.

Jian Ding, Jaroslaw Blasiok, Jelani Nelson

CoRR, 2017

BPTree: An ℓ₂ Heavy Hitters Algorithm Using Constant Memory.

Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff

Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

Optimality of the Johnson-Lindenstrauss Lemma.

Kasper Green Larsen, Jelani Nelson

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams.

Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Continuous Monitoring of l_p Norms in Data Streams.

Jaroslaw Blasiok, Jian Ding, Jelani Nelson

Proceedings of the Approximation, 2017

2016

Oblivious Subspace Embeddings.

Jelani Nelson

Encyclopedia of Algorithms, 2016

Sorting and Selection with Imprecise Comparisons.

Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson

ACM Trans. Algorithms, 2016

Chaining introduction with some computer science applications.

Jelani Nelson

Bull. EATCS, 2016

The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction.

Kasper Green Larsen, Jelani Nelson

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Optimal Approximate Matrix Product in Terms of Stable Rank.

Michael B. Cohen, Jelani Nelson, David P. Woodruff

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm.

Jaroslaw Blasiok, Jelani Nelson

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms.

Kasper Green Larsen, Jelani Nelson, Huy L. Nguyên

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space.

Jean Bourgain, Sjoerd Dirksen, Jelani Nelson

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Sparser Johnson-Lindenstrauss Transforms.

Daniel M. Kane, Jelani Nelson

J. ACM, 2014

New constructions of RIP matrices with fast multiplication and fewer rows.

Jelani Nelson, Eric Price, Mary Wootters

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Lower Bounds for Oblivious Subspace Embeddings.

Jelani Nelson, Huy L. Nguyên

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Toward a unified theory of sparse dimensionality reduction in Euclidean space.

Jean Bourgain, Jelani Nelson

CoRR, 2013

Sparsity lower bounds for dimensionality reducing maps.

Jelani Nelson, Huy L. Nguyen

Proceedings of the Symposium on Theory of Computing Conference, 2013

OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings.

Jelani Nelson, Huy L. Nguyen

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Sketching and streaming algorithms for processing massive data.

Jelani Nelson

XRDS, 2012

On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation.

Jelani Nelson, Huy L. Nguyên, David P. Woodruff

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Sketching and streaming algorithms.

Jelani Nelson

PhD thesis, 2011

Fast moment estimation in data streams in optimal space.

Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Almost Optimal Explicit Johnson-Lindenstrauss Families.

Daniel Kane, Raghu Meka, Jelani Nelson

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

A Derandomized Sparse Johnson-Lindenstrauss Transform.

Daniel M. Kane, Jelani Nelson

Electron. Colloquium Comput. Complex., 2010

Almost Optimal Explicit Johnson-Lindenstrauss Transformations.

Daniel Kane, Raghu Meka, Jelani Nelson

Electron. Colloquium Comput. Complex., 2010

A Sparser Johnson-Lindenstrauss Transform

Daniel M. Kane, Jelani Nelson

CoRR, 2010

On the Exact Space Complexity of Sketching and Streaming Small Norms.

Daniel M. Kane, Jelani Nelson, David P. Woodruff

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Fast Manhattan sketches in data streams.

Jelani Nelson, David P. Woodruff

Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

An optimal algorithm for the distinct elements problem.

Daniel M. Kane, Jelani Nelson, David P. Woodruff

Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

2009

Bounded Independence Fools Degree-2 Threshold Functions.

Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson

Electron. Colloquium Comput. Complex., 2009

A Near-Optimal Algorithm for L1-Difference

Jelani Nelson, David P. Woodruff

CoRR, 2009

Dynamic ham-sandwich cuts in the plane.

Timothy G. Abbott, Michael A. Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel Kane, Stefan Langerman, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, Vincent Yeung

Comput. Geom., 2009

2008

Revisiting Norm Estimation in Data Streams

Daniel M. Kane, Jelani Nelson, David P. Woodruff

CoRR, 2008

Streaming algorithms for estimating entropy.

Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak

Proceedings of the 2008 IEEE Information Theory Workshop, 2008

Sketching and Streaming Entropy via Approximation Theory.

Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

A Note on Set Cover Inapproximability Independent of Universe Size.

Jelani Nelson

Electron. Colloquium Comput. Complex., 2007

Cache-oblivious streaming B-trees.

Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel, Bradley C. Kuszmaul, Jelani Nelson

Proceedings of the SPAA 2007: Proceedings of the 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2007

2005

Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane.

Timothy G. Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, Vincent Yeung

Proceedings of the 17th Canadian Conference on Computational Geometry, 2005