[photo by Eliza Grinnell]
Jelani Nelson
Harvard John A. Paulson School of Engineering and Applied Sciences
Maxwell Dworkin 125
33 Oxford St.
Cambridge, MA 02138
minilek@seas.harvard.edu
Associate Professor, Computer Science. Member of the Theory of Computation group.
CV
Teaching
CS 125. Algorithms & Complexity. Fall 2016.
CS 224. Advanced Algorithms. Fall 2014, Spring 2017.
CS 124. Data Structures and Algorithms. Spring 2014, 2015.
CS 229r. Algorithms for Big Data. Fall 2013, 2015.
Current students: Jarosław Błasiok, Vasileios Nakos, Zhengyu Wang.
Postdocs: Rasmus Kyng (Jan 2018–), Kyle Luh, Huacheng Yu (co-hosted with Madhu Sudan)
Former postdocs:
Jakub Pachocki (2016-17, now Researcher at OpenAI).
Yi Li (2014-2015, now Asst. Prof. in the Division of Mathematical Sciences at Nanyang Technological University).
Some notes on sketching and streaming algorithms from the TUM Summer School on Mathematical Methods for High-Dimensional Data Analysis.
Some notes on dimensionality reduction from the MADALGO Summer School on Streaming Algorithms.
Website for a workshop on chaining and applications to computer science, which I co-organized (with Assaf Naor) in June 2016.
Papers
- 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. [ps][pdf][arXiv] (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. [ps][pdf][arXiv]
- Tom Morgan, Jelani Nelson. A note on reductions between compressed sensing guarantees. Manuscript [ps][pdf][arXiv][notes]
- 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. [ps][pdf][arXiv]
- 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. [ps][pdf][arXiv][notes]
- Jelani Nelson. Chaining introduction with some computer science applications. The Algorithmics Column, Bulletin of EATCS, vol. 120, 2016. [EATCS]
- 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]
USVICoder
AddisCoder
Theory StackExchange
Great Game
Nimble Fingers