Jelani Nelson - RankMe

126 papers A* 39A 6B 3Journal 69Unranked 7

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Adaptively Robust Resettable Streaming. CoRR Edith Cohen, Elena Gribelyuk, Jelani Nelson, Uri Stemmer
2026	A*	`conf`	One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches. SODA Edith Cohen, Jelani Nelson, Tamás Sarlós, Mihir Singhal, Uri Stemmer
2025	A	`conf`	Space Complexity of Minimum Cut Problems in Single-Pass Streams. ITCS Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff
2024	A*	`conf`	Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries. COLT Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2024	J	`jnl`	Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries. CoRR Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2024	J	`jnl`	Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries. IACR Cryptol. ePrint Arch. Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2024	A	`conf`	On the Amortized Complexity of Approximate Counting. APPROX/RANDOM Ishaq Aden-Ali, Yanjun Han, Jelani Nelson, Huacheng Yu
2024	J	`jnl`	One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches. CoRR Edith Cohen, Jelani Nelson, Tamás Sarlós, Mihir Singhal, Uri Stemmer
2024	A*	`conf`	Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages. ICML Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar, Samson Zhou
2024	J	`jnl`	Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages. CoRR Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar, Samson Zhou
2024	J	`jnl`	Space Complexity of Minimum Cut Problems in Single-Pass Streams. CoRR Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff
2024	A*	`conf`	Sparse Dimensionality Reduction Revisited. ICML Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn
2024	J	`jnl`	Terminal Embeddings in Sublinear Time. TheoretiCS Yeshwanth Cherapanamjeri, Jelani Nelson
2023	A	`conf`	Differentially Private Aggregation via Imperfect Shuffling. ITC Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou
2023	J	`jnl`	Differentially Private Aggregation via Imperfect Shuffling. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson, Samson Zhou
2023	A*	`conf`	Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. SODA Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu
2023	A*	`conf`	Fast Optimal Locally Private Mean Estimation via Random Projections. NeurIPS Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar
2023	J	`jnl`	Fast Optimal Locally Private Mean Estimation via Random Projections. CoRR Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar
2023	A	`conf`	Generalized Private Selection and Testing with High Confidence. ITCS Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2023	J	`jnl`	Hot PATE: Private Aggregation of Distributions for Diverse Task. CoRR Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2023	A*	`conf`	Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization. STOC Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2023	A	`conf`	Private Counting of Distinct and k-Occurring Items in Time Windows. ITCS Badih Ghazi, Ravi Kumar, Jelani Nelson, Pasin Manurangsi
2023	J	`jnl`	Sparse Dimensionality Reduction Revisited. CoRR Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, Chris Schwiegelshohn
2023	A*	`conf`	Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs. AAAI Edith Cohen, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2022	J	`jnl`	Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson
2022	A*	`conf`	Estimation of Entropy in Constant Space with Improved Sample Complexity. NeurIPS Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
2022	J	`jnl`	Estimation of Entropy in Constant Space with Improved Sample Complexity. CoRR Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
2022	J	`jnl`	Generalized Private Selection and Testing with High Confidence. CoRR Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2022	A*	`conf`	On the Robustness of CountSketch to Adaptive Inputs. ICML Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, Uri Stemmer
2022	J	`jnl`	On the Robustness of CountSketch to Adaptive Inputs. CoRR Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, Uri Stemmer
2022	J	`jnl`	On the amortized complexity of approximate counting. CoRR Ishaq Aden-Ali, Yanjun Han, Jelani Nelson, Huacheng Yu
2022	A*	`conf`	Optimal Bounds for Approximate Counting. PODS Jelani Nelson, Huacheng Yu
2022	J	`jnl`	Private Counting of Distinct and k-Occurring Items in Time Windows. CoRR Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson
2022	J	`jnl`	Private Frequency Estimation via Projective Geometry. CoRR Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar
2022	A*	`conf`	Private frequency estimation via projective geometry. ICML Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar
2022	A*	`conf`	Sketching based Representations for Robust Image Classification with Provable Guarantees. NeurIPS Nishanth Dikkala, Sankeerth Rao Karingula, Raghu Meka, Jelani Nelson, Rina Panigrahy, Xin Wang
2022	J	`jnl`	Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs. CoRR Edith Cohen, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2022	J	`jnl`	Uniform Approximations for Randomized Hadamard Transforms with Applications. CoRR Yeshwanth Cherapanamjeri, Jelani Nelson
2022	A*	`conf`	Uniform approximations for Randomized Hadamard Transforms with applications. STOC Yeshwanth Cherapanamjeri, Jelani Nelson
2022	J	`jnl`	Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization. CoRR Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer
2021	A	`conf`	An Improved Sketching Algorithm for Edit Distance. STACS Ce Jin, Jelani Nelson, Kewen Wu
2021	J	`jnl`	Randomized Algorithms for Scientific Computing (RASC). CoRR Aydin Buluç, Tamara G. Kolda, Stefan M. Wild, Mihai Anitescu, Anthony M. DeGennaro, John Jakeman, Chandrika Kamath, Ramakrishnan Kannan, Miles E. Lopes, Per-Gunnar Martinsson, Kary L. Myers, Jelani Nelson, Juan M. Restrepo, C. Seshadhri, Draguna L. Vrabie, Brendt Wohlberg, Stephen J. Wright, Chao Yang, Peter Zwart
2021	A*	`conf`	Terminal Embeddings in Sublinear Time. FOCS Yeshwanth Cherapanamjeri, Jelani Nelson
2021	J	`jnl`	Terminal Embeddings in Sublinear Time. CoRR Yeshwanth Cherapanamjeri, Jelani Nelson
2021	J	`jnl`	Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020. CoRR Shuchi Chawla, Jelani Nelson, Chris Umans, David P. Woodruff
2020	J	`jnl`	An Improved Sketching Bound for Edit Distance. CoRR Ce Jin, Jelani Nelson, Kewen Wu
2020	A*	`conf`	On Adaptive Distance Estimation. NeurIPS Yeshwanth Cherapanamjeri, Jelani Nelson
2020	J	`jnl`	On Adaptive Distance Estimation. CoRR Yeshwanth Cherapanamjeri, Jelani Nelson
2020	J	`jnl`	Optimal bounds for approximate counting. CoRR Jelani Nelson, Huacheng Yu
2019	J	`jnl`	Heavy Hitters and the Structure of Local Privacy. ACM Trans. Algorithms Mark Bun, Jelani Nelson, Uri Stemmer
2019	J	`jnl`	Heavy hitters via cluster-preserving clustering. Commun. ACM Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
2019	A*	`conf`	Margin-Based Generalization Lower Bounds for Boosted Classifiers. NeurIPS Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson
2019	J	`jnl`	Margin-Based Generalization Lower Bounds for Boosted Classifiers. CoRR Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, Jelani Nelson
2019	A*	`conf`	Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. SODA Jelani Nelson, Huacheng Yu
2019	A*	`conf`	Optimal terminal dimensionality reduction in Euclidean space. STOC Shyam Narayanan, Jelani Nelson
2018	B	`conf`	A Note on Reductions Between Compressed Sensing Guarantees. ISIT Tom Morgan, Jelani Nelson
2018	A*	`conf`	Heavy Hitters and the Structure of Local Privacy. PODS Mark Bun, Jelani Nelson, Uri Stemmer
2018	J	`jnl`	Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. CoRR Jelani Nelson, Huacheng Yu
2018	J	`jnl`	Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation. Electron. Colloquium Comput. Complex. Jelani Nelson, Huacheng Yu
2018	J	`jnl`	Optimal terminal dimensionality reduction in Euclidean space. CoRR Shyam Narayanan, Jelani Nelson
2018	—	`conf`	Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. SOSA Michael B. Cohen, T. S. Jayram, Jelani Nelson
2017	A*	`conf`	BPTree: An ℓ PODS Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff
2017	—	`conf`	Continuous Monitoring of l_p Norms in Data Streams. APPROX-RANDOM Jaroslaw Blasiok, Jian Ding, Jelani Nelson
2017	J	`jnl`	Continuous monitoring of 𝓁 CoRR Jian Ding, Jaroslaw Blasiok, Jelani Nelson
2017	J	`jnl`	Fillable arrays with constant time operations and a single bit of redundancy. CoRR Jacob Teo Por Loong, Jelani Nelson, Huacheng Yu
2017	J	`jnl`	Heavy Hitters and the Structure of Local Privacy. CoRR Mark Bun, Jelani Nelson, Uri Stemmer
2017	A*	`conf`	Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. FOCS Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh
2017	J	`jnl`	Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams. CoRR Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh
2017	J	`jnl`	Optimal lower bounds for universal relation, samplers, and finding duplicates. CoRR Jelani Nelson, Jakub Pachocki, Zhengyu Wang
2017	A*	`conf`	Optimality of the Johnson-Lindenstrauss Lemma. FOCS Kasper Green Larsen, Jelani Nelson
2016	J	`jnl`	A note on reductions between compressed sensing guarantees. CoRR Tom Morgan, Jelani Nelson
2016	A*	`conf`	An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm. ICALP Jaroslaw Blasiok, Jelani Nelson
2016	J	`jnl`	An improved analysis of the ER-SpUD dictionary learning algorithm. CoRR Jaroslaw Blasiok, Jelani Nelson
2016	J	`jnl`	BPTree: an ℓ CoRR Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff
2016	J	`jnl`	Chaining introduction with some computer science applications. Bull. EATCS Jelani Nelson
2016	A*	`conf`	Heavy Hitters via Cluster-Preserving Clustering. FOCS Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
2016	J	`jnl`	Heavy hitters via cluster-preserving clustering. CoRR Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup
2016	—	`ch.`	Oblivious Subspace Embeddings. Encyclopedia of Algorithms Jelani Nelson
2016	A*	`conf`	Optimal Approximate Matrix Product in Terms of Stable Rank. ICALP Michael B. Cohen, Jelani Nelson, David P. Woodruff
2016	J	`jnl`	Optimality of the Johnson-Lindenstrauss Lemma. CoRR Kasper Green Larsen, Jelani Nelson
2016	J	`jnl`	Sorting and Selection with Imprecise Comparisons. ACM Trans. Algorithms Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
2016	A*	`conf`	The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction. ICALP Kasper Green Larsen, Jelani Nelson
2015	J	`jnl`	Optimal approximate matrix product in terms of stable rank. CoRR Michael B. Cohen, Jelani Nelson, David P. Woodruff
2015	J	`jnl`	Sorting and Selection with Imprecise Comparisons. CoRR Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
2015	A*	`conf`	Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms. STOC Kasper Green Larsen, Jelani Nelson, Huy L. Nguyên
2015	A*	`conf`	Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space. STOC Jean Bourgain, Sjoerd Dirksen, Jelani Nelson
2014	—	`conf`	Lower Bounds for Oblivious Subspace Embeddings. ICALP (1) Jelani Nelson, Huy L. Nguyên
2014	A*	`conf`	New constructions of RIP matrices with fast multiplication and fewer rows. SODA Jelani Nelson, Eric Price, Mary Wootters
2014	J	`jnl`	Sparser Johnson-Lindenstrauss Transforms. J. ACM Daniel M. Kane, Jelani Nelson
2014	J	`jnl`	The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction. CoRR Kasper Green Larsen, Jelani Nelson
2014	J	`jnl`	Time lower bounds for nonadaptive turnstile streaming algorithms. CoRR Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen
2013	J	`jnl`	Lower bounds for oblivious subspace embeddings. CoRR Jelani Nelson, Huy L. Nguyen
2013	A*	`conf`	OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings. FOCS Jelani Nelson, Huy L. Nguyen
2013	A*	`conf`	Sparsity lower bounds for dimensionality reducing maps. STOC Jelani Nelson, Huy L. Nguyen
2013	J	`jnl`	Toward a unified theory of sparse dimensionality reduction in Euclidean space. CoRR Jean Bourgain, Jelani Nelson
2012	J	`jnl`	New constructions of RIP matrices with fast multiplication and fewer rows CoRR Jelani Nelson, Eric Price, Mary Wootters
2012	J	`jnl`	OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings CoRR Jelani Nelson, Huy L. Nguyen
2012	J	`jnl`	On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation CoRR Jelani Nelson, Huy L. Nguyên, David P. Woodruff
2012	—	`conf`	On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. APPROX-RANDOM Jelani Nelson, Huy L. Nguyên, David P. Woodruff
2012	J	`jnl`	Sketching and streaming algorithms for processing massive data. XRDS Jelani Nelson
2012	A*	`conf`	Sparser Johnson-Lindenstrauss transforms. SODA Daniel M. Kane, Jelani Nelson
2012	J	`jnl`	Sparsity Lower Bounds for Dimensionality Reducing Maps CoRR Jelani Nelson, Huy L. Nguyen
2011	—	`conf`	Almost Optimal Explicit Johnson-Lindenstrauss Families. APPROX-RANDOM Daniel Kane, Raghu Meka, Jelani Nelson
2011	A*	`conf`	Fast moment estimation in data streams in optimal space. STOC Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff
2011	—	`—`	Sketching and streaming algorithms. Jelani Nelson
2010	J	`jnl`	A Derandomized Sparse Johnson-Lindenstrauss Transform CoRR Daniel M. Kane, Jelani Nelson
2010	J	`jnl`	A Derandomized Sparse Johnson-Lindenstrauss Transform. Electron. Colloquium Comput. Complex. Daniel M. Kane, Jelani Nelson
2010	J	`jnl`	A Sparser Johnson-Lindenstrauss Transform CoRR Daniel M. Kane, Jelani Nelson
2010	J	`jnl`	Almost Optimal Explicit Johnson-Lindenstrauss Transformations. Electron. Colloquium Comput. Complex. Daniel Kane, Raghu Meka, Jelani Nelson
2010	A*	`conf`	An optimal algorithm for the distinct elements problem. PODS Daniel M. Kane, Jelani Nelson, David P. Woodruff
2010	A*	`conf`	Bounded Independence Fools Degree-2 Threshold Functions. FOCS Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson
2010	A*	`conf`	Fast Manhattan sketches in data streams. PODS Jelani Nelson, David P. Woodruff
2010	J	`jnl`	Fast Moment Estimation in Data Streams in Optimal Space CoRR Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff
2010	A*	`conf`	On the Exact Space Complexity of Sketching and Streaming Small Norms. SODA Daniel M. Kane, Jelani Nelson, David P. Woodruff
2009	J	`jnl`	A Near-Optimal Algorithm for L1-Difference CoRR Jelani Nelson, David P. Woodruff
2009	J	`jnl`	Bounded Independence Fools Degree-2 Threshold Functions CoRR Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson
2009	J	`jnl`	Bounded Independence Fools Degree-2 Threshold Functions. Electron. Colloquium Comput. Complex. Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson
2009	J	`jnl`	Dynamic ham-sandwich cuts in the plane. Comput. Geom. Timothy G. Abbott, Michael A. Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel Kane, Stefan Langerman, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, Vincent Yeung
2009	—	`conf`	Sorting and Selection with Imprecise Comparisons. ICALP (1) Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
2008	J	`jnl`	Revisiting Norm Estimation in Data Streams CoRR Daniel M. Kane, Jelani Nelson, David P. Woodruff
2008	J	`jnl`	Sketching and Streaming Entropy via Approximation Theory CoRR Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak
2008	A*	`conf`	Sketching and Streaming Entropy via Approximation Theory. FOCS Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak
2008	B	`conf`	Streaming algorithms for estimating entropy. ITW Nicholas J. A. Harvey, Jelani Nelson, Krzysztof Onak
2007	J	`jnl`	A Note on Set Cover Inapproximability Independent of Universe Size. Electron. Colloquium Comput. Complex. Jelani Nelson
2007	B	`conf`	Cache-oblivious streaming B-trees. SPAA Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel, Bradley C. Kuszmaul, Jelani Nelson
2005	—	`conf`	Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane. CCCG Timothy G. Abbott, Erik D. Demaine, Martin L. Demaine, Daniel Kane, Stefan Langerman, Jelani Nelson, Vincent Yeung