JN

Jelani Nelson

0000-0001-7370-3733

cs.DScs.LGcs.ITmath.ITcs.CRcs.CCcs.CGstat.MLmath.PRcs.DM

On Valency

published · living versions

Complexity of Differentially Private Selection via Federated APIs

with Hilal Asi, Vitaly Feldman, Huy L. Nguyen, Kunal Talwar +1

1 version

W_ncvbjvg7v1 · current

Preprints & journals

55 papers in the corpus · 2008–2026

A Matrix Factorization Approach in Turnstile Streaming

Jan Bulanek, Ravi Kumar, Raghu Meka et al.

0 citations

2607.28819v12026arXiv

Adaptively Robust Resettable Streaming

Edith Cohen, Elena Gribelyuk, Jelani Nelson et al.

0 citations

2601.21989v12026arXiv

Space Complexity of Minimum Cut Problems in Single-Pass Streams

Matthew Ding, Alexandro Garces, Jason Li et al.

0 citations

2412.01143v22024arXiv

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches

Edith Cohen, Jelani Nelson, Tam'as Sarl'os et al.

0 citations

2411.06370v22024arXiv

Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages

Hilal Asi, Vitaly Feldman, Jelani Nelson et al.

1 citation

2404.10201v22024arXiv

Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries

Edith Cohen, Xin Lyu, Jelani Nelson et al.

1 citation

2403.00028v22024arXiv

Hot PATE: Private Aggregation of Distributions for Diverse Task

Edith Cohen, Benjamin Cohen-Wang, Xin Lyu et al.

0 citations

2312.02132v42023arXiv

Differentially Private Aggregation via Imperfect Shuffling

Badih Ghazi, Ravi Kumar, Pasin Manurangsi et al.

10 citations

2308.14733v12023arXiv

Fast Optimal Locally Private Mean Estimation via Random Projections

Hilal Asi, Vitaly Feldman, Jelani Nelson et al.

4 citations

2306.04444v22023arXiv

Sparse Dimensionality Reduction Revisited

Mikael M\oller H\ogsgaard, Lion Kamma, Kasper Green Larsen et al.

0 citations

2302.06165v12023arXiv

Generalized Private Selection and Testing with High Confidence

Edith Cohen, Xin Lyu, Jelani Nelson et al.

0 citations

2211.12063v22022arXiv

Private Counting of Distinct and k-Occurring Items in Time Windows

Badih Ghazi, Ravi Kumar, Pasin Manurangsi et al.

3 citations

2211.11718v12022arXiv

Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization

Edith Cohen, Xin Lyu, Jelani Nelson et al.

5 citations

2211.06387v12022arXiv

On the amortized complexity of approximate counting

Ishaq Aden-Ali, Yanjun Han, Jelani Nelson et al.

0 citations

2211.03917v12022arXiv

Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs

Edith Cohen, Jelani Nelson, Tam'as Sarl'os et al.

6 citations

2207.00956v22022arXiv

Estimation of Entropy in Constant Space with Improved Sample Complexity

Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson et al.

2 citations

2205.09804v12022arXiv

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds

Badih Ghazi, Ravi Kumar, Pasin Manurangsi et al.

5 citations

2203.16476v12022arXiv

Uniform Approximations for Randomized Hadamard Transforms with Applications

Yeshwanth Cherapanamjeri, Jelani Nelson

2 citations

2203.01599v12022arXiv

Private Frequency Estimation via Projective Geometry

Vitaly Feldman, Jelani Nelson, Huy Le Nguyen et al.

10 citations

2203.00194v12022arXiv

On the Robustness of CountSketch to Adaptive Inputs

Edith Cohen, Xin Lyu, Jelani Nelson et al.

4 citations

2202.13736v12022arXiv

Terminal Embeddings in Sublinear Time

Yeshwanth Cherapanamjeri, Jelani Nelson

1 citation

2110.08691v32021TheoretiCS, Volume 3 (March 14, 2024) theoretics:9167

Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020

Shuchi Chawla, Jelani Nelson, Chris Umans et al.

0 citations

2107.02846v12021arXiv

Randomized Algorithms for Scientific Computing (RASC)

Aydin Buluc, Tamara G. Kolda, Stefan M. Wild et al.

11 citations

2104.11079v32021arXiv

An Improved Sketching Algorithm for Edit Distance

Ce Jin, Jelani Nelson, Kewen Wu

2 citations

2010.13170v32020arXiv

On Adaptive Distance Estimation

Yeshwanth Cherapanamjeri, Jelani Nelson

8 citations

2010.11252v22020arXiv

Optimal bounds for approximate counting

Jelani Nelson, Huacheng Yu

10 citations

2010.02116v22020arXiv

Margin-Based Generalization Lower Bounds for Boosted Classifiers

Allan Gr\onlund, Lior Kamma, Kasper Green Larsen et al.

11 citations

1909.12518v42019arXiv

Optimal terminal dimensionality reduction in Euclidean space

Shyam Narayanan, Jelani Nelson

28 citations

1810.09250v12018arXiv

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Jelani Nelson, Huacheng Yu

10 citations

1807.05135v32018arXiv

Heavy Hitters and the Structure of Local Privacy

Mark Bun, Jelani Nelson, Uri Stemmer

91 citations

1711.04740v12017arXiv

Continuous monitoring of $\ell_p$ norms in data streams

Jaros\law B\lasiok, Jian Ding, Jelani Nelson

3 citations

1704.06710v32017arXiv

Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams

Michael Kapralov, Jelani Nelson, Jakub Pachocki et al.

28 citations

1704.00633v12017arXiv

Optimal lower bounds for universal relation, samplers, and finding duplicates

Jelani Nelson, Jakub Pachocki, Zhengyu Wang

5 citations

1703.08139v12017arXiv

Optimality of the Johnson-Lindenstrauss Lemma

Kasper Green Larsen, Jelani Nelson

90 citations

1609.02094v22016arXiv

A note on reductions between compressed sensing guarantees

Tom Morgan, Jelani Nelson

0 citations

1606.00757v22016arXiv

Heavy hitters via cluster-preserving clustering

Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen et al.

56 citations

1604.01357v12016arXiv

BPTree: an $\ell_2$ heavy hitters algorithm using constant memory

Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin et al.

10 citations

1603.00759v42016arXiv

An improved analysis of the ER-SpUD dictionary learning algorithm

Jaros\law B\lasiok, Jelani Nelson

8 citations

1602.05719v12016arXiv

Optimal approximate matrix product in terms of stable rank

Michael B. Cohen, Jelani Nelson, David P. Woodruff

89 citations

1507.02268v32015arXiv

Sorting and Selection with Imprecise Comparisons

Miklos Ajtai, Vitaly Feldman, Avinatan Hassidim et al.

33 citations

1501.02911v12015arXiv

The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction

Kasper Green Larsen, Jelani Nelson

37 citations

1411.2404v12014arXiv

Time lower bounds for nonadaptive turnstile streaming algorithms

Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen

12 citations

1407.2151v12014arXiv

Toward a unified theory of sparse dimensionality reduction in Euclidean space

Jean Bourgain, Sjoerd Dirksen, Jelani Nelson

85 citations

1311.2542v42013Geometric and Functional Analysis 25 (2015), no. 4, 1009-1088

Lower bounds for oblivious subspace embeddings

Jelani Nelson, Huy L. Nguyen

36 citations

1308.3280v12013arXiv

New constructions of RIP matrices with fast multiplication and fewer rows

Jelani Nelson, Eric Price, Mary Wootters

29 citations

1211.0986v12012arXiv

Sparsity Lower Bounds for Dimensionality Reducing Maps

Jelani Nelson, Huy L. Nguyen

2 citations

1211.0995v12012arXiv

OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings

Jelani Nelson, Huy L. Nguyen

259 citations

1211.1002v12012arXiv

On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation

Jelani Nelson, Huy Nguyen, David P. Woodruff

20 citations

1206.5725v12012arXiv

Sparser Johnson-Lindenstrauss Transforms

Daniel M. Kane, Jelani Nelson

0 citations

1012.1577v62010arXiv

Fast Moment Estimation in Data Streams in Optimal Space

Daniel M. Kane, Jelani Nelson, Ely Porat et al.

82 citations

1007.4191v12010arXiv

Career total: 129 works. 55 are in this corpus.Showing the 50 most recent.

Profile built from the corpus for this byline.

129

works

2,557

citations

27

h-index

Corpus papers per year

Author records are still filling in while the Hub is in beta. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.