Jelani Nelson

35 Olden St. Princeton, NJ 08540 minilek@seas.harvard.edu Postdoctoral researcher at Princeton University and the Institute for Advanced Study. Formerly I was a Ph.D. student in the MIT CSAIL Theory of Computation group working with Prof. Erik Demaine and Prof. Piotr Indyk, an MEng. student in the SuperTech group under the direction of Dr. Bradley Kuszmaul and Prof. Charles Leiserson, an undergraduate at MIT living in Bexley Hall and studying Computer Science and Mathematics, and a gradeschooler at All Saints Cathedral School from 1st to 12th grade.

Papers

• Daniel M. Kane, Jelani Nelson. Sparser Johnson-Lindenstrauss Transforms. 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]


• 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]