Ce Jin, Jelani Nelson, Kewen Wu. An improved sketching bound for edit distance.

*Manuscript*Jelani Nelson, Huacheng Yu. Optimal bounds for approximate counting.

*Manuscript*Yeshwanth Cherapanamjeri, Jelani Nelson. On Adaptive Distance Estimation.

*Proceedings of the 32nd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS 2020)*, Vancouver, BC, Canada, December 7-12, 2020.**Spotlight Presentation**.Allan Grønlund Jørgensen, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson. Margin-Based Generalization Lower Bounds for Boosted Classifiers.

*Proceedings of the 31st Annual Conference on Advances in Neural Information Processing Systems (NeurIPS 2019)*, Vancouver, BC, Canada, December 10-12, 2019.Shyam Narayanan, Jelani Nelson. Optimal terminal dimensionality reduction in Euclidean space.

*Proceedings of the 51st ACM Symposium on Theory of Computing (STOC 2019)*, Phoeniz, AZ, June 23-26, 2019.Jelani Nelson, Huacheng Yu. Optimal lower bounds for distributed and streaming spanning forest computation.

*Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)*, San Diego, California, January 6-9, 2019.Mark Bun, Jelani Nelson, Uri Stemmer. Heavy hitters and the structure of local privacy.

*Proceedings of the 36th Annual ACM Symposium on Principles of Database Systems (PODS 2018)*, Houston, TX, June 10-15, 2018.Jacob Teo Por Loong, Jelani Nelson, Huacheng Yu. Fillable arrays with constant time operations and a single bit of redundancy.

*Manuscript*Tom Morgan, Jelani Nelson. A note on reductions between compressed sensing guarantees.

*Proceedings of the 2018 International Symposium on Information Theory (ISIT 2018)*, Vail, CO, June 17-22, 2018.Michael B. Cohen, T.S. Jayram, Jelani Nelson. Simple analyses of the Sparse Johnson-Lindenstrauss transform.

*Proceedings of the 1st Annual Symposium on Simplicity in Algorithms (SOSA 2018)*, New Orleans, LA, January 7-10, 2018.Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh. Optimal lower bounds for universal relation, samplers, and finding duplicates in streams.

*Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017)*, Berkeley, CA, October 15-17, 2017. (merger of work of Nelson, Pachocki, and Wang, and of work of Kapralov, Woodruff, and Yahyazadeh)Kasper Green Larsen, Jelani Nelson. Optimality of the Johnson-Lindenstrauss lemma.

*Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017)*, Berkeley, CA, October 15-17, 2017.Jarosław Błasiok, Jian Ding, Jelani Nelson. Continuous monitoring of ℓ

_{p}norms in data streams.*Proceedings of the 21st International Workshop on Randomization and Computation (RANDOM 2017)*, Berkeley, CA, August 16-18, 2017.Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff. BPTree: an ℓ

_{2}heavy hitters algorithm using constant memory.*Proceedings of the 36th Annual ACM Symposium on Principles of Database Systems (PODS 2017)*, Chicago, IL, May 14-19, 2017.Jelani Nelson. Chaining introduction with some computer science applications.

*The Algorithmics Column, Bulletin of EATCS*, vol. 120, 2016.Kasper Green Larsen, Jelani Nelson, Nguyễn Lê Huy, Mikkel Thorup. Heavy hitters via cluster-preserving clustering.

*Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)*, New Brunswick, NJ, October 9-11, 2016.Jarosław Błasiok, Jelani Nelson. An improved analysis of the ER-SpUD dictionary learning algorithm.

*Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016)*, Rome, Italy, July 12-15, 2016.Michael B. Cohen, Jelani Nelson, David P. Woodruff. Optimal approximate matrix product in terms of stable rank.

*Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016)*, Rome, Italy, July 12-15, 2016.Kasper Green Larsen, Jelani Nelson. The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction.

*Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016)*, Rome, Italy, July 12-15, 2016.Kasper Green Larsen, Jelani Nelson, Nguyễn Lê Huy. Time lower bounds for nonadaptive turnstile streaming algorithms.

*Proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015)*, Portland, OR, June 14-17, 2015.Jean Bourgain, Sjoerd Dirksen, Jelani Nelson. Toward a unified theory of sparse dimensionality reduction in Euclidean space.

*Geometric and Functional Analysis (GAFA)*, 25(4): 1009-1088, 2015. Preliminary version in*Proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015)*, Portland, OR, June 14-17, 2015.Jelani Nelson, Nguyễn Lê Huy. Lower bounds for oblivious subspace embeddings.

*Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014)*, Copenhagen, Denmark, July 8-11, 2014.Jelani Nelson, Eric Price, Mary Wootters. New constructions of RIP matrices with fast multiplication and fewer rows.

*Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)*, Portland, Oregon, January 5-7, 2014.Jelani Nelson, Nguyễn Lê Huy. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings.

*Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013)*, Berkeley, CA, October 27-29, 2013.Jelani Nelson, Nguyễn Lê Huy. Sparsity lower bounds for dimensionality reducing maps.

*Proceedings of the 45th ACM Symposium on Theory of Computing (STOC 2013)*, Palo Alto, CA, June 1-4, 2013.Jelani Nelson, Nguyễn Lê Huy, David P. Woodruff. On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation.

*Linear Algebra and its Applications, Special Issue on Sparse Approximate Solution of Linear Systems*, 441: 152-167, January 15, 2014. Preliminary version in*Proceedings of the 16th International Workshop on Randomization and Computation (RANDOM 2012)*, Cambridge, MA, August 15-17, 2012.Jelani Nelson. Sketching and streaming algorithms for processing massive data.

*ACM Crossroads*, 19(1): 14-19, 2012. ACM Digital LibraryDaniel M. Kane, Jelani Nelson. Sparser Johnson-Lindenstrauss Transforms.

*Journal of the ACM*, 61(1): Article No. 4, 2014. Preliminary version in*Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)*, Kyoto, Japan, January 17-19, 2012.Daniel M. Kane, Raghu Meka, Jelani Nelson. Almost Optimal Explicit Johnson-Lindenstrauss Transformations.

*Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM 2011)*, Princeton, NJ, August 17-19, 2011.Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff. Fast Moment Estimation in Data Streams in Optimal Space.

*Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC 2011)*, San Jose, CA, June 6-8, 2011.Daniel M. Kane, Jelani Nelson. A Derandomized Sparse Johnson-Lindenstrauss Transform.

*Manuscript*.Daniel M. Kane, Jelani Nelson, David P. Woodruff. An Optimal Algorithm for the Distinct Elements Problem.

*Proceedings of the 29th Annual ACM Symposium on Principles of Database Systems (PODS 2010)*, Indianapolis, IN, June 6-10, 2010.**PODS Best Paper Award**,**IBM Research Pat Goldberg Memorial Best Paper Award**, invited to*Journal of the ACM*.Jelani Nelson, David P. Woodruff. Fast Manhattan Sketches in Data Streams.

*Proceedings of the 29th Annual ACM Symposium on Principles of Database Systems (PODS 2010)*, Indianapolis, IN, June 6-10, 2010.Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson. Bounded Independence Fools Degree-2 Threshold Functions.

*Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)*, Las Vegas, NV, October 23-26, 2010.Daniel M. Kane, Jelani Nelson, David P. Woodruff. On the Exact Space Complexity of Sketching and Streaming Small Norms.

*Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)*, Austin, TX, January 17-19, 2010.Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson. Sorting and Selection with Imprecise Comparisons.

*Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009)*, Rhodes, Greece, July 5-12, 2009.Jelani Nelson, David P. Woodruff. A Near-Optimal Algorithm for L1-Difference.

*Manuscript*.Timothy G. Abbott, Michael A. Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel M. Kane, Stefan Langerman, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, Vincent Yeung. Dynamic Ham-Sandwich Cuts in the Plane.

*Computational Geometry: Theory And Applications (CGTA)*, 42(5): 419-428, 2009.

Preliminary version in*Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005)*, August 10-12, Windsor, Ontario, Canada, 2005.Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak, Sketching and Streaming Entropy via Approximation Theory.

*Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008)*, Philadelphia, PA, October 26-28, 2008.Jelani Nelson. A Note on Set Cover Inapproximability Independent of Universe Size.

*Electronic Colloquium on Computational Complexity (ECCC), TR07-105*, 2007.Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan Fogel, Bradley C. Kuszmaul, Jelani Nelson. Cache-Oblivious Streaming B-trees.

*Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures SPAA 2007*, San Diego, CA, June 9-11, 2007.Jelani Nelson. Sketching and Streaming High-Dimensional Vectors. Ph.D. Thesis.

**George M. Sprowls Award**, given for the best doctoral theses in computer science at MIT.Jelani Nelson. External-Memory Search Trees with Fast Insertions. M.Eng. Thesis.