[photo by Eliza Grinnell]

Jelani Nelson

Assistant Professor, Computer Science. Member of the Theory of Computation group.
CV

Teaching

Papers

• Kasper Green Larsen, Jelani Nelson. Optimality of the Johnson-Lindenstrauss lemma. Manuscript [ps][pdf][arXiv]


• Tom Morgan, Jelani Nelson. A note on reductions between compressed sensing guarantees. Manuscript [ps][pdf][arXiv][notes]


• Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff. BPTree: an ℓ₂ heavy hitters algorithm using constant memory. Manuscript [ps][pdf][arXiv][notes]


• 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. [ps][pdf][arXiv]


• 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. [ps][pdf][arXiv]


• 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. [ps][pdf][arXiv][notes]


• 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. [ps][pdf][arXiv]


• 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. [ps][pdf][arXiv]


• 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. [ps][pdf][arXiv][notes]


• 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. [ps][pdf][arXiv]


• 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. [ps][pdf][arXiv]


• 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. [ps][pdf][arXiv]


• 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. [ps][pdf][arXiv]


• 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. [ps][pdf][arXiv]


• Jelani Nelson. Sketching and streaming algorithms for processing massive data. ACM Crossroads, 19(1): 14-19, 2012. [ps][pdf][ACM Digital Library]


• Daniel 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. [conf_ps][conf_pdf][full_ps][full_pdf][arXiv][notes]


• 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. [ps][pdf][ECCC]


• 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. [ps][pdf][arXiv]


• Daniel M. Kane, Jelani Nelson. A Derandomized Sparse Johnson-Lindenstrauss Transform. Manuscript. [ps][pdf][arXiv][ECCC][notes]


• 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. [ps][pdf]


• 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. [ps][pdf]


• 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. [conf_ps][conf_pdf] [full_ps][full_pdf][arXiv][ECCC][notes]


• 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. [ps][pdf][notes]


• 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. [ps][pdf][full_ps][full_pdf][arXiv]


• Jelani Nelson, David P. Woodruff. A Near-Optimal Algorithm for L1-Difference. Manuscript. [ps][pdf][arXiv]


• 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. [ps][pdf]
  Preliminary version in Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG 2005), August 10-12, Windsor, Ontario, Canada, 2005. [ps][pdf]


• 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. [ps][pdf][arXiv][notes]


• Jelani Nelson. A Note on Set Cover Inapproximability Independent of Universe Size. Electronic Colloquium on Computational Complexity (ECCC), TR07-105, 2007. [ps][pdf]


• 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. [ps][pdf][notes]


• Jelani Nelson. Sketching and Streaming High-Dimensional Vectors. Ph.D. Thesis. [ps][pdf]
  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. [ps][pdf]