Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff. Space Complexity of Minimum Cut Problems in Single-Pass Streams. Proceedings of the 16th Annual Conference on Innovations in Theoretical (ITCS 2025), New York, NY, January 7-10, 2025.
Ishaq Aden-Ali, Yanjun Han, Jelani Nelson, Huacheng Yu. On the amortized complexity of approximate counting. Proceedings of the 28th International Workshop on Randomization and Computation (RANDOM 2024), London, UK, August 28-30, 2024.
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer. Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries. Proceedings of the 37th Annual Conference on Learning Theory (COLT 2024), Edmonton, Canada, June 30-July 3, 2024.
Hilal Asi, Vitaly Feldman, Jelani Nelson, Nguyễn Lê Huy, Kunal Talwar, Samson Zhou. Private vector mean estimation in the shuffle model: optimal rates require many messages. Proceedings of the 41st International Conference on Machine Learning (ICML 2024), Vienna, Austria, July 21-27, 2024.
Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn. Sparse Dimensionality Reduction Revisited. Proceedings of the 41st International Conference on Machine Learning (ICML 2024), Vienna, Austria, July 21-27, 2024.
Hilal Asi, Vitaly Feldman, Jelani Nelson, Nguyễn Lê Huy, Kunal Talwar. Fast optimal locally private mean estimation via random projections. Proceedings of the 33rd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS 2023), New Orleans, LA, December 10-16, 2023.
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou. Differentially Private Aggregation via Imperfect Shuffling. Proceedings of the 4th Annual Conference on Information-Theoretic Cryptography (ITC 2023), Aarhus, Denmark, June 6-8, 2023 (also non-archival track of the 4th Annual Symposium on Foundations of Responsible Computing (FORC 2023), Stanford, CA, June 7-9, 2023).
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer. Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization. Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2023), Orlando, FL, June 20-23, 2023.
Edith Cohen, Jelani Nelson, Tamás Sarlós, Uri Stemmer. Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs. Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023), Washington, DC, February 7-14, 2023.
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer. Generalized Private Selection and Testing with High Confidence. Proceedings of the 14th Annual Conference on Innovations in Theoretical (ITCS 2023), Cambridge, MA, January 11-13, 2023.
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson. Private Counting of Distinct and k-Occurring Items in Time Windows. Proceedings of the 14th Annual Conference on Innovations in Theoretical (ITCS 2023), Cambridge, MA, January 11-13, 2023.
Justin Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu. Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, January 22-25, 2023. (merger of work of Ghazi, Kumar, Manurangsi, and Nelson, and of work of Chen, Narayanan, and Xu)
Nishanth Dikkala, Sankeerth Rao Karingula, Raghu Meka, Jelani Nelson, Rina Panigrahy, Xin Wang. Sketching based Representations for Robust Image Classification with Provable Guarantees. Proceedings of the 32nd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS 2022), New Orleans, LA, November 28-December 9, 2022.
Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten. Estimation of Entropy in Constant Space with Improved Sample Complexity. Proceedings of the 32nd Annual Conference on Advances in Neural Information Processing Systems (NeurIPS 2022), New Orleans, LA, November 28-December 9, 2022.
Vitaly Feldman, Jelani Nelson, Nguyễn Lê Huy, Kunal Talwar. Private Frequency Estimation via Projective Geometry. Proceedings of the 39th International Conference on Machine Learning (ICML 2022), Baltimore, MD, July 17-23, 2022.
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, Uri Stemmer. On the Robustness of CountSketch to Adaptive Inputs. Proceedings of the 39th International Conference on Machine Learning (ICML 2022), Baltimore, MD, July 17-23, 2022.
Jelani Nelson, Huacheng Yu. Optimal bounds for approximate counting. Proceedings of the 40th Annual ACM Symposium on Principles of Database Systems (PODS 2022), Philadelphia, PA, June 12-17, 2022. PODS Best Paper Award.
Yeshwanth Cherapanamjeri, Jelani Nelson. Uniform approximations for Randomized Hadamard Transforms with applications. Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022), Rome, Italy, June 20-24, 2022.
Yeshwanth Cherapanamjeri, Jelani Nelson. Terminal embeddings in sublinear time. Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021), Denver, CO, February 7-10, 2022.
Ce Jin, Jelani Nelson, Kewen Wu. An improved sketching bound for edit distance. Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Saarbrücken, Germany, March 16-19, 2021.
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 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.
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.