Jelani Nelson

According to our database1, Jelani Nelson authored at least 47 papers between 2005 and 2019.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Heavy Hitters and the Structure of Local Privacy.
ACM Trans. Algorithms, 2019

Heavy hitters via cluster-preserving clustering.
Commun. ACM, 2019

Optimal terminal dimensionality reduction in Euclidean space.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Margin-Based Generalization Lower Bounds for Boosted Classifiers.
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.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Simple Analyses of the Sparse Johnson-Lindenstrauss Transform.
Proceedings of the 1st Symposium on Simplicity in Algorithms, 2018

A Note on Reductions Between Compressed Sensing Guarantees.
Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

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

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

Continuous monitoring of 𝓁p norms in data streams.
CoRR, 2017

BPTree: An ℓ2 Heavy Hitters Algorithm Using Constant Memory.
Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2017

Optimality of the Johnson-Lindenstrauss Lemma.
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.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Continuous Monitoring of l_p Norms in Data Streams.
Proceedings of the Approximation, 2017

2016
Oblivious Subspace Embeddings.
Encyclopedia of Algorithms, 2016

Sorting and Selection with Imprecise Comparisons.
ACM Trans. Algorithms, 2016

Chaining introduction with some computer science applications.
Bulletin of the EATCS, 2016

The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Optimal Approximate Matrix Product in Terms of Stable Rank.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms.
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.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014
Sparser Johnson-Lindenstrauss Transforms.
J. ACM, 2014

New constructions of RIP matrices with fast multiplication and fewer rows.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Lower Bounds for Oblivious Subspace Embeddings.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

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

Sparsity lower bounds for dimensionality reducing maps.
Proceedings of the Symposium on Theory of Computing Conference, 2013

OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012
Sketching and streaming algorithms for processing massive data.
ACM Crossroads, 2012

On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
Sketching and streaming algorithms.
PhD thesis, 2011

Fast moment estimation in data streams in optimal space.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Almost Optimal Explicit Johnson-Lindenstrauss Families.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
A Derandomized Sparse Johnson-Lindenstrauss Transform.
Electronic Colloquium on Computational Complexity (ECCC), 2010

A Sparser Johnson-Lindenstrauss Transform
CoRR, 2010

On the Exact Space Complexity of Sketching and Streaming Small Norms.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Fast Manhattan sketches in data streams.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

An optimal algorithm for the distinct elements problem.
Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010

2009
Bounded Independence Fools Degree-2 Threshold Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2009

A Near-Optimal Algorithm for L1-Difference
CoRR, 2009

Dynamic ham-sandwich cuts in the plane.
Comput. Geom., 2009

2008
Revisiting Norm Estimation in Data Streams
CoRR, 2008

Streaming algorithms for estimating entropy.
Proceedings of the 2008 IEEE Information Theory Workshop, 2008

Sketching and Streaming Entropy via Approximation Theory.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
A Note on Set Cover Inapproximability Independent of Universe Size.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Cache-oblivious streaming B-trees.
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.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005


  Loading...