default search action
BibTeX records: Jelani Nelson
@article{DBLP:journals/theoretics/CherapanamjeriN24, author = {Yeshwanth Cherapanamjeri and Jelani Nelson}, title = {Terminal Embeddings in Sublinear Time}, journal = {TheoretiCS}, volume = {3}, year = {2024}, url = {https://doi.org/10.46298/theoretics.24.6}, doi = {10.46298/THEORETICS.24.6}, timestamp = {Tue, 02 Apr 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/theoretics/CherapanamjeriN24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/approx/Aden-AliHNY24, author = {Ishaq Aden{-}Ali and Yanjun Han and Jelani Nelson and Huacheng Yu}, editor = {Amit Kumar and Noga Ron{-}Zewi}, title = {On the Amortized Complexity of Approximate Counting}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, {APPROX/RANDOM} 2024, August 28-30, 2024, London School of Economics, London, {UK}}, series = {LIPIcs}, volume = {317}, pages = {33:1--33:17}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2024}, url = {https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.33}, doi = {10.4230/LIPICS.APPROX/RANDOM.2024.33}, timestamp = {Mon, 16 Sep 2024 17:07:54 +0200}, biburl = {https://dblp.org/rec/conf/approx/Aden-AliHNY24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/colt/Cohen0NSS24, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Uri Stemmer}, editor = {Shipra Agrawal and Aaron Roth}, title = {Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries}, booktitle = {The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada}, series = {Proceedings of Machine Learning Research}, volume = {247}, pages = {1200--1222}, publisher = {{PMLR}}, year = {2024}, url = {https://proceedings.mlr.press/v247/cohen24b.html}, timestamp = {Fri, 05 Jul 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/colt/Cohen0NSS24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icml/AsiFNNTZ24, author = {Hilal Asi and Vitaly Feldman and Jelani Nelson and Huy L. Nguyen and Kunal Talwar and Samson Zhou}, title = {Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages}, booktitle = {Forty-first International Conference on Machine Learning, {ICML} 2024, Vienna, Austria, July 21-27, 2024}, publisher = {OpenReview.net}, year = {2024}, url = {https://openreview.net/forum?id=PTGJOUlQ68}, timestamp = {Mon, 02 Sep 2024 16:45:29 +0200}, biburl = {https://dblp.org/rec/conf/icml/AsiFNNTZ24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icml/HogsgaardKLNS24, author = {Mikael M{\o}ller H{\o}gsgaard and Lior Kamma and Kasper Green Larsen and Jelani Nelson and Chris Schwiegelshohn}, title = {Sparse Dimensionality Reduction Revisited}, booktitle = {Forty-first International Conference on Machine Learning, {ICML} 2024, Vienna, Austria, July 21-27, 2024}, publisher = {OpenReview.net}, year = {2024}, url = {https://openreview.net/forum?id=ufgVvFmUom}, timestamp = {Mon, 02 Sep 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/icml/HogsgaardKLNS24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2403-00028, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Uri Stemmer}, title = {Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries}, journal = {CoRR}, volume = {abs/2403.00028}, year = {2024}, url = {https://doi.org/10.48550/arXiv.2403.00028}, doi = {10.48550/ARXIV.2403.00028}, eprinttype = {arXiv}, eprint = {2403.00028}, timestamp = {Tue, 02 Apr 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2403-00028.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2404-10201, author = {Hilal Asi and Vitaly Feldman and Jelani Nelson and Huy L. Nguyen and Kunal Talwar and Samson Zhou}, title = {Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages}, journal = {CoRR}, volume = {abs/2404.10201}, year = {2024}, url = {https://doi.org/10.48550/arXiv.2404.10201}, doi = {10.48550/ARXIV.2404.10201}, eprinttype = {arXiv}, eprint = {2404.10201}, timestamp = {Wed, 15 May 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2404-10201.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/iacr/CohenLNSS24, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Uri Stemmer}, title = {Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries}, journal = {{IACR} Cryptol. ePrint Arch.}, pages = {373}, year = {2024}, url = {https://eprint.iacr.org/2024/373}, timestamp = {Mon, 18 Mar 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/iacr/CohenLNSS24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/aaai/CohenNSS23, author = {Edith Cohen and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Uri Stemmer}, editor = {Brian Williams and Yiling Chen and Jennifer Neville}, title = {Tricking the Hashing Trick: {A} Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs}, booktitle = {Thirty-Seventh {AAAI} Conference on Artificial Intelligence, {AAAI} 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, {IAAI} 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, {EAAI} 2023, Washington, DC, USA, February 7-14, 2023}, pages = {7235--7243}, publisher = {{AAAI} Press}, year = {2023}, url = {https://doi.org/10.1609/aaai.v37i6.25882}, doi = {10.1609/AAAI.V37I6.25882}, timestamp = {Mon, 04 Sep 2023 12:29:24 +0200}, biburl = {https://dblp.org/rec/conf/aaai/CohenNSS23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/citc/Ghazi0MNZ23, author = {Badih Ghazi and Ravi Kumar and Pasin Manurangsi and Jelani Nelson and Samson Zhou}, editor = {Kai{-}Min Chung}, title = {Differentially Private Aggregation via Imperfect Shuffling}, booktitle = {4th Conference on Information-Theoretic Cryptography, {ITC} 2023, June 6-8, 2023, Aarhus University, Aarhus, Denmark}, series = {LIPIcs}, volume = {267}, pages = {17:1--17:22}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2023}, url = {https://doi.org/10.4230/LIPIcs.ITC.2023.17}, doi = {10.4230/LIPICS.ITC.2023.17}, timestamp = {Wed, 21 Aug 2024 22:46:00 +0200}, biburl = {https://dblp.org/rec/conf/citc/Ghazi0MNZ23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/innovations/Cohen0NSS23, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Uri Stemmer}, editor = {Yael Tauman Kalai}, title = {Generalized Private Selection and Testing with High Confidence}, booktitle = {14th Innovations in Theoretical Computer Science Conference, {ITCS} 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, {USA}}, series = {LIPIcs}, volume = {251}, pages = {39:1--39:23}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2023}, url = {https://doi.org/10.4230/LIPIcs.ITCS.2023.39}, doi = {10.4230/LIPICS.ITCS.2023.39}, timestamp = {Wed, 21 Aug 2024 22:46:00 +0200}, biburl = {https://dblp.org/rec/conf/innovations/Cohen0NSS23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/innovations/Ghazi0NM23, author = {Badih Ghazi and Ravi Kumar and Jelani Nelson and Pasin Manurangsi}, editor = {Yael Tauman Kalai}, title = {Private Counting of Distinct and k-Occurring Items in Time Windows}, booktitle = {14th Innovations in Theoretical Computer Science Conference, {ITCS} 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, {USA}}, series = {LIPIcs}, volume = {251}, pages = {55:1--55:24}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2023}, url = {https://doi.org/10.4230/LIPIcs.ITCS.2023.55}, doi = {10.4230/LIPICS.ITCS.2023.55}, timestamp = {Thu, 02 Feb 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/innovations/Ghazi0NM23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/nips/AsiFNNT23, author = {Hilal Asi and Vitaly Feldman and Jelani Nelson and Huy L. Nguyen and Kunal Talwar}, editor = {Alice Oh and Tristan Naumann and Amir Globerson and Kate Saenko and Moritz Hardt and Sergey Levine}, title = {Fast Optimal Locally Private Mean Estimation via Random Projections}, booktitle = {Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023}, year = {2023}, url = {http://papers.nips.cc/paper\_files/paper/2023/hash/34822dab66c13f0100017b8ea373038a-Abstract-Conference.html}, timestamp = {Fri, 01 Mar 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/nips/AsiFNNT23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/soda/ChenG0MNNX23, author = {Justin Y. Chen and Badih Ghazi and Ravi Kumar and Pasin Manurangsi and Shyam Narayanan and Jelani Nelson and Yinzhan Xu}, editor = {Nikhil Bansal and Viswanath Nagarajan}, title = {Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds}, booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2023, Florence, Italy, January 22-25, 2023}, pages = {5040--5067}, publisher = {{SIAM}}, year = {2023}, url = {https://doi.org/10.1137/1.9781611977554.ch184}, doi = {10.1137/1.9781611977554.CH184}, timestamp = {Fri, 17 Feb 2023 09:28:57 +0100}, biburl = {https://dblp.org/rec/conf/soda/ChenG0MNNX23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/Cohen0NSS23, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Uri Stemmer}, editor = {Barna Saha and Rocco A. Servedio}, title = {Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization}, booktitle = {Proceedings of the 55th Annual {ACM} Symposium on Theory of Computing, {STOC} 2023, Orlando, FL, USA, June 20-23, 2023}, pages = {472--482}, publisher = {{ACM}}, year = {2023}, url = {https://doi.org/10.1145/3564246.3585148}, doi = {10.1145/3564246.3585148}, timestamp = {Mon, 22 May 2023 13:01:48 +0200}, biburl = {https://dblp.org/rec/conf/stoc/Cohen0NSS23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2302-06165, author = {Mikael M{\o}ller H{\o}gsgaard and Lior Kamma and Kasper Green Larsen and Jelani Nelson and Chris Schwiegelshohn}, title = {Sparse Dimensionality Reduction Revisited}, journal = {CoRR}, volume = {abs/2302.06165}, year = {2023}, url = {https://doi.org/10.48550/arXiv.2302.06165}, doi = {10.48550/ARXIV.2302.06165}, eprinttype = {arXiv}, eprint = {2302.06165}, timestamp = {Mon, 20 Feb 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2302-06165.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2306-04444, author = {Hilal Asi and Vitaly Feldman and Jelani Nelson and Huy L. Nguyen and Kunal Talwar}, title = {Fast Optimal Locally Private Mean Estimation via Random Projections}, journal = {CoRR}, volume = {abs/2306.04444}, year = {2023}, url = {https://doi.org/10.48550/arXiv.2306.04444}, doi = {10.48550/ARXIV.2306.04444}, eprinttype = {arXiv}, eprint = {2306.04444}, timestamp = {Tue, 13 Jun 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2306-04444.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2308-14733, author = {Badih Ghazi and Ravi Kumar and Pasin Manurangsi and Jelani Nelson and Samson Zhou}, title = {Differentially Private Aggregation via Imperfect Shuffling}, journal = {CoRR}, volume = {abs/2308.14733}, year = {2023}, url = {https://doi.org/10.48550/arXiv.2308.14733}, doi = {10.48550/ARXIV.2308.14733}, eprinttype = {arXiv}, eprint = {2308.14733}, timestamp = {Mon, 04 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2308-14733.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2312-02132, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Uri Stemmer}, title = {Hot {PATE:} Private Aggregation of Distributions for Diverse Task}, journal = {CoRR}, volume = {abs/2312.02132}, year = {2023}, url = {https://doi.org/10.48550/arXiv.2312.02132}, doi = {10.48550/ARXIV.2312.02132}, eprinttype = {arXiv}, eprint = {2312.02132}, timestamp = {Tue, 12 Dec 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2312-02132.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icml/Cohen0NSSS22, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Moshe Shechner and Uri Stemmer}, editor = {Kamalika Chaudhuri and Stefanie Jegelka and Le Song and Csaba Szepesv{\'{a}}ri and Gang Niu and Sivan Sabato}, title = {On the Robustness of CountSketch to Adaptive Inputs}, booktitle = {International Conference on Machine Learning, {ICML} 2022, 17-23 July 2022, Baltimore, Maryland, {USA}}, series = {Proceedings of Machine Learning Research}, volume = {162}, pages = {4112--4140}, publisher = {{PMLR}}, year = {2022}, url = {https://proceedings.mlr.press/v162/cohen22a.html}, timestamp = {Tue, 12 Jul 2022 17:36:52 +0200}, biburl = {https://dblp.org/rec/conf/icml/Cohen0NSSS22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icml/FeldmanNNT22, author = {Vitaly Feldman and Jelani Nelson and Huy L. Nguyen and Kunal Talwar}, editor = {Kamalika Chaudhuri and Stefanie Jegelka and Le Song and Csaba Szepesv{\'{a}}ri and Gang Niu and Sivan Sabato}, title = {Private frequency estimation via projective geometry}, booktitle = {International Conference on Machine Learning, {ICML} 2022, 17-23 July 2022, Baltimore, Maryland, {USA}}, series = {Proceedings of Machine Learning Research}, volume = {162}, pages = {6418--6433}, publisher = {{PMLR}}, year = {2022}, url = {https://proceedings.mlr.press/v162/feldman22a.html}, timestamp = {Tue, 23 Aug 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/icml/FeldmanNNT22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/nips/AliakbarpourMNW22, author = {Maryam Aliakbarpour and Andrew McGregor and Jelani Nelson and Erik Waingarten}, editor = {Sanmi Koyejo and S. Mohamed and A. Agarwal and Danielle Belgrave and K. Cho and A. Oh}, title = {Estimation of Entropy in Constant Space with Improved Sample Complexity}, booktitle = {Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022}, year = {2022}, url = {http://papers.nips.cc/paper\_files/paper/2022/hash/d13a3eae72366e61dfdc7eea82eeb685-Abstract-Conference.html}, timestamp = {Mon, 08 Jan 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/nips/AliakbarpourMNW22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/nips/DikkalaKMNPW22, author = {Nishanth Dikkala and Sankeerth Rao Karingula and Raghu Meka and Jelani Nelson and Rina Panigrahy and Xin Wang}, editor = {Sanmi Koyejo and S. Mohamed and A. Agarwal and Danielle Belgrave and K. Cho and A. Oh}, title = {Sketching based Representations for Robust Image Classification with Provable Guarantees}, booktitle = {Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022}, year = {2022}, url = {http://papers.nips.cc/paper\_files/paper/2022/hash/2439ec22091b9d6cfbebf3284b40116e-Abstract-Conference.html}, timestamp = {Mon, 08 Jan 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/nips/DikkalaKMNPW22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/pods/NelsonY22, author = {Jelani Nelson and Huacheng Yu}, editor = {Leonid Libkin and Pablo Barcel{\'{o}}}, title = {Optimal Bounds for Approximate Counting}, booktitle = {{PODS} '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022}, pages = {119--127}, publisher = {{ACM}}, year = {2022}, url = {https://doi.org/10.1145/3517804.3526225}, doi = {10.1145/3517804.3526225}, timestamp = {Wed, 15 Jun 2022 08:52:54 +0200}, biburl = {https://dblp.org/rec/conf/pods/NelsonY22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/CherapanamjeriN22, author = {Yeshwanth Cherapanamjeri and Jelani Nelson}, editor = {Stefano Leonardi and Anupam Gupta}, title = {Uniform approximations for Randomized Hadamard Transforms with applications}, booktitle = {{STOC} '22: 54th Annual {ACM} {SIGACT} Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022}, pages = {659--671}, publisher = {{ACM}}, year = {2022}, url = {https://doi.org/10.1145/3519935.3519961}, doi = {10.1145/3519935.3519961}, timestamp = {Tue, 27 Dec 2022 09:06:31 +0100}, biburl = {https://dblp.org/rec/conf/stoc/CherapanamjeriN22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2202-13736, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Moshe Shechner and Uri Stemmer}, title = {On the Robustness of CountSketch to Adaptive Inputs}, journal = {CoRR}, volume = {abs/2202.13736}, year = {2022}, url = {https://arxiv.org/abs/2202.13736}, eprinttype = {arXiv}, eprint = {2202.13736}, timestamp = {Fri, 25 Mar 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2202-13736.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2203-00194, author = {Vitaly Feldman and Jelani Nelson and Huy Le Nguyen and Kunal Talwar}, title = {Private Frequency Estimation via Projective Geometry}, journal = {CoRR}, volume = {abs/2203.00194}, year = {2022}, url = {https://doi.org/10.48550/arXiv.2203.00194}, doi = {10.48550/ARXIV.2203.00194}, eprinttype = {arXiv}, eprint = {2203.00194}, timestamp = {Wed, 16 Mar 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2203-00194.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2203-01599, author = {Yeshwanth Cherapanamjeri and Jelani Nelson}, title = {Uniform Approximations for Randomized Hadamard Transforms with Applications}, journal = {CoRR}, volume = {abs/2203.01599}, year = {2022}, url = {https://doi.org/10.48550/arXiv.2203.01599}, doi = {10.48550/ARXIV.2203.01599}, eprinttype = {arXiv}, eprint = {2203.01599}, timestamp = {Wed, 16 Mar 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2203-01599.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2203-16476, author = {Badih Ghazi and Ravi Kumar and Pasin Manurangsi and Jelani Nelson}, title = {Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds}, journal = {CoRR}, volume = {abs/2203.16476}, year = {2022}, url = {https://doi.org/10.48550/arXiv.2203.16476}, doi = {10.48550/ARXIV.2203.16476}, eprinttype = {arXiv}, eprint = {2203.16476}, timestamp = {Mon, 04 Apr 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2203-16476.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2205-09804, author = {Maryam Aliakbarpour and Andrew McGregor and Jelani Nelson and Erik Waingarten}, title = {Estimation of Entropy in Constant Space with Improved Sample Complexity}, journal = {CoRR}, volume = {abs/2205.09804}, year = {2022}, url = {https://doi.org/10.48550/arXiv.2205.09804}, doi = {10.48550/ARXIV.2205.09804}, eprinttype = {arXiv}, eprint = {2205.09804}, timestamp = {Mon, 06 Nov 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2205-09804.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2207-00956, author = {Edith Cohen and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Uri Stemmer}, title = {Tricking the Hashing Trick: {A} Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs}, journal = {CoRR}, volume = {abs/2207.00956}, year = {2022}, url = {https://doi.org/10.48550/arXiv.2207.00956}, doi = {10.48550/ARXIV.2207.00956}, eprinttype = {arXiv}, eprint = {2207.00956}, timestamp = {Wed, 06 Jul 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2207-00956.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2211-03917, author = {Ishaq Aden{-}Ali and Yanjun Han and Jelani Nelson and Huacheng Yu}, title = {On the amortized complexity of approximate counting}, journal = {CoRR}, volume = {abs/2211.03917}, year = {2022}, url = {https://doi.org/10.48550/arXiv.2211.03917}, doi = {10.48550/ARXIV.2211.03917}, eprinttype = {arXiv}, eprint = {2211.03917}, timestamp = {Wed, 09 Nov 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2211-03917.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2211-06387, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Uri Stemmer}, title = {{\~{O}}ptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization}, journal = {CoRR}, volume = {abs/2211.06387}, year = {2022}, url = {https://doi.org/10.48550/arXiv.2211.06387}, doi = {10.48550/ARXIV.2211.06387}, eprinttype = {arXiv}, eprint = {2211.06387}, timestamp = {Tue, 15 Nov 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2211-06387.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2211-11718, author = {Badih Ghazi and Ravi Kumar and Pasin Manurangsi and Jelani Nelson}, title = {Private Counting of Distinct and k-Occurring Items in Time Windows}, journal = {CoRR}, volume = {abs/2211.11718}, year = {2022}, url = {https://doi.org/10.48550/arXiv.2211.11718}, doi = {10.48550/ARXIV.2211.11718}, eprinttype = {arXiv}, eprint = {2211.11718}, timestamp = {Thu, 24 Nov 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2211-11718.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2211-12063, author = {Edith Cohen and Xin Lyu and Jelani Nelson and Tam{\'{a}}s Sarl{\'{o}}s and Uri Stemmer}, title = {Generalized Private Selection and Testing with High Confidence}, journal = {CoRR}, volume = {abs/2211.12063}, year = {2022}, url = {https://doi.org/10.48550/arXiv.2211.12063}, doi = {10.48550/ARXIV.2211.12063}, eprinttype = {arXiv}, eprint = {2211.12063}, timestamp = {Thu, 24 Nov 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2211-12063.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/CherapanamjeriN21, author = {Yeshwanth Cherapanamjeri and Jelani Nelson}, title = {Terminal Embeddings in Sublinear Time}, booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS} 2021, Denver, CO, USA, February 7-10, 2022}, pages = {1209--1216}, publisher = {{IEEE}}, year = {2021}, url = {https://doi.org/10.1109/FOCS52979.2021.00118}, doi = {10.1109/FOCS52979.2021.00118}, timestamp = {Wed, 09 Mar 2022 12:12:23 +0100}, biburl = {https://dblp.org/rec/conf/focs/CherapanamjeriN21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stacs/JinN021, author = {Ce Jin and Jelani Nelson and Kewen Wu}, editor = {Markus Bl{\"{a}}ser and Benjamin Monmege}, title = {An Improved Sketching Algorithm for Edit Distance}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science, {STACS} 2021, March 16-19, 2021, Saarbr{\"{u}}cken, Germany (Virtual Conference)}, series = {LIPIcs}, volume = {187}, pages = {45:1--45:16}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2021}, url = {https://doi.org/10.4230/LIPIcs.STACS.2021.45}, doi = {10.4230/LIPICS.STACS.2021.45}, timestamp = {Wed, 21 Aug 2024 22:46:00 +0200}, biburl = {https://dblp.org/rec/conf/stacs/JinN021.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2104-11079, author = {Aydin Bulu{\c{c}} and Tamara G. Kolda and Stefan M. Wild and Mihai Anitescu and Anthony M. DeGennaro and John Jakeman and Chandrika Kamath and Ramakrishnan Kannan and Miles E. Lopes and Per{-}Gunnar Martinsson and Kary L. Myers and Jelani Nelson and Juan M. Restrepo and C. Seshadhri and Draguna L. Vrabie and Brendt Wohlberg and Stephen J. Wright and Chao Yang and Peter Zwart}, title = {Randomized Algorithms for Scientific Computing {(RASC)}}, journal = {CoRR}, volume = {abs/2104.11079}, year = {2021}, url = {https://arxiv.org/abs/2104.11079}, eprinttype = {arXiv}, eprint = {2104.11079}, timestamp = {Fri, 06 Oct 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2104-11079.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2107-02846, author = {Shuchi Chawla and Jelani Nelson and Chris Umans and David P. Woodruff}, title = {Visions in Theoretical Computer Science: {A} Report on the {TCS} Visioning Workshop 2020}, journal = {CoRR}, volume = {abs/2107.02846}, year = {2021}, url = {https://arxiv.org/abs/2107.02846}, eprinttype = {arXiv}, eprint = {2107.02846}, timestamp = {Thu, 22 Jul 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2107-02846.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2110-08691, author = {Yeshwanth Cherapanamjeri and Jelani Nelson}, title = {Terminal Embeddings in Sublinear Time}, journal = {CoRR}, volume = {abs/2110.08691}, year = {2021}, url = {https://arxiv.org/abs/2110.08691}, eprinttype = {arXiv}, eprint = {2110.08691}, timestamp = {Fri, 22 Oct 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2110-08691.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/nips/CherapanamjeriN20, author = {Yeshwanth Cherapanamjeri and Jelani Nelson}, editor = {Hugo Larochelle and Marc'Aurelio Ranzato and Raia Hadsell and Maria{-}Florina Balcan and Hsuan{-}Tien Lin}, title = {On Adaptive Distance Estimation}, booktitle = {Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual}, year = {2020}, url = {https://proceedings.neurips.cc/paper/2020/hash/803ef56843860e4a48fc4cdb3065e8ce-Abstract.html}, timestamp = {Tue, 19 Jan 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/nips/CherapanamjeriN20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2010-02116, author = {Jelani Nelson and Huacheng Yu}, title = {Optimal bounds for approximate counting}, journal = {CoRR}, volume = {abs/2010.02116}, year = {2020}, url = {https://arxiv.org/abs/2010.02116}, eprinttype = {arXiv}, eprint = {2010.02116}, timestamp = {Mon, 12 Oct 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2010-02116.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2010-11252, author = {Yeshwanth Cherapanamjeri and Jelani Nelson}, title = {On Adaptive Distance Estimation}, journal = {CoRR}, volume = {abs/2010.11252}, year = {2020}, url = {https://arxiv.org/abs/2010.11252}, eprinttype = {arXiv}, eprint = {2010.11252}, timestamp = {Mon, 26 Oct 2020 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-2010-11252.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-2010-13170, author = {Ce Jin and Jelani Nelson and Kewen Wu}, title = {An Improved Sketching Bound for Edit Distance}, journal = {CoRR}, volume = {abs/2010.13170}, year = {2020}, url = {https://arxiv.org/abs/2010.13170}, eprinttype = {arXiv}, eprint = {2010.13170}, timestamp = {Wed, 19 Jul 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-2010-13170.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/cacm/LarsenNNT19, author = {Kasper Green Larsen and Jelani Nelson and Huy L. Nguyen and Mikkel Thorup}, title = {Heavy hitters via cluster-preserving clustering}, journal = {Commun. {ACM}}, volume = {62}, number = {8}, pages = {95--100}, year = {2019}, url = {https://doi.org/10.1145/3339185}, doi = {10.1145/3339185}, timestamp = {Fri, 09 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/cacm/LarsenNNT19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/talg/BunNS19, author = {Mark Bun and Jelani Nelson and Uri Stemmer}, title = {Heavy Hitters and the Structure of Local Privacy}, journal = {{ACM} Trans. Algorithms}, volume = {15}, number = {4}, pages = {51:1--51:40}, year = {2019}, url = {https://doi.org/10.1145/3344722}, doi = {10.1145/3344722}, timestamp = {Wed, 23 Oct 2019 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/talg/BunNS19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/nips/GronlundKLMN19, author = {Allan Gr{\o}nlund and Lior Kamma and Kasper Green Larsen and Alexander Mathiasen and Jelani Nelson}, editor = {Hanna M. Wallach and Hugo Larochelle and Alina Beygelzimer and Florence d'Alch{\'{e}}{-}Buc and Emily B. Fox and Roman Garnett}, title = {Margin-Based Generalization Lower Bounds for Boosted Classifiers}, booktitle = {Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada}, pages = {11940--11949}, year = {2019}, url = {https://proceedings.neurips.cc/paper/2019/hash/e1dc4bf1f94e87fdfeb2d91ae3dc10ef-Abstract.html}, timestamp = {Mon, 16 May 2022 15:41:51 +0200}, biburl = {https://dblp.org/rec/conf/nips/GronlundKLMN19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/soda/NelsonY19, author = {Jelani Nelson and Huacheng Yu}, editor = {Timothy M. Chan}, title = {Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation}, booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9, 2019}, pages = {1844--1860}, publisher = {{SIAM}}, year = {2019}, url = {https://doi.org/10.1137/1.9781611975482.111}, doi = {10.1137/1.9781611975482.111}, timestamp = {Thu, 15 Jul 2021 13:49:01 +0200}, biburl = {https://dblp.org/rec/conf/soda/NelsonY19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/NarayananN19, author = {Shyam Narayanan and Jelani Nelson}, editor = {Moses Charikar and Edith Cohen}, title = {Optimal terminal dimensionality reduction in Euclidean space}, booktitle = {Proceedings of the 51st Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC} 2019, Phoenix, AZ, USA, June 23-26, 2019}, pages = {1064--1069}, publisher = {{ACM}}, year = {2019}, url = {https://doi.org/10.1145/3313276.3316307}, doi = {10.1145/3313276.3316307}, timestamp = {Sat, 22 Jun 2019 17:42:26 +0200}, biburl = {https://dblp.org/rec/conf/stoc/NarayananN19.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1909-12518, author = {Allan Gr{\o}nlund and Lior Kamma and Kasper Green Larsen and Alexander Mathiasen and Jelani Nelson}, title = {Margin-Based Generalization Lower Bounds for Boosted Classifiers}, journal = {CoRR}, volume = {abs/1909.12518}, year = {2019}, url = {http://arxiv.org/abs/1909.12518}, eprinttype = {arXiv}, eprint = {1909.12518}, timestamp = {Wed, 02 Oct 2019 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1909-12518.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/isit/MorganN18, author = {Tom Morgan and Jelani Nelson}, title = {A Note on Reductions Between Compressed Sensing Guarantees}, booktitle = {2018 {IEEE} International Symposium on Information Theory, {ISIT} 2018, Vail, CO, USA, June 17-22, 2018}, pages = {411--415}, publisher = {{IEEE}}, year = {2018}, url = {https://doi.org/10.1109/ISIT.2018.8437489}, doi = {10.1109/ISIT.2018.8437489}, timestamp = {Wed, 16 Oct 2019 14:14:48 +0200}, biburl = {https://dblp.org/rec/conf/isit/MorganN18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/pods/BunNS18, author = {Mark Bun and Jelani Nelson and Uri Stemmer}, editor = {Jan Van den Bussche and Marcelo Arenas}, title = {Heavy Hitters and the Structure of Local Privacy}, booktitle = {Proceedings of the 37th {ACM} {SIGMOD-SIGACT-SIGAI} Symposium on Principles of Database Systems, Houston, TX, USA, June 10-15, 2018}, pages = {435--447}, publisher = {{ACM}}, year = {2018}, url = {https://doi.org/10.1145/3196959.3196981}, doi = {10.1145/3196959.3196981}, timestamp = {Sat, 19 Oct 2019 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/pods/BunNS18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/soda/CohenJN18, author = {Michael B. Cohen and T. S. Jayram and Jelani Nelson}, editor = {Raimund Seidel}, title = {Simple Analyses of the Sparse Johnson-Lindenstrauss Transform}, booktitle = {1st Symposium on Simplicity in Algorithms, {SOSA} 2018, January 7-10, 2018, New Orleans, LA, {USA}}, series = {OASIcs}, volume = {61}, pages = {15:1--15:9}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2018}, url = {https://doi.org/10.4230/OASIcs.SOSA.2018.15}, doi = {10.4230/OASICS.SOSA.2018.15}, timestamp = {Wed, 21 Aug 2024 22:46:00 +0200}, biburl = {https://dblp.org/rec/conf/soda/CohenJN18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1807-05135, author = {Jelani Nelson and Huacheng Yu}, title = {Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation}, journal = {CoRR}, volume = {abs/1807.05135}, year = {2018}, url = {http://arxiv.org/abs/1807.05135}, eprinttype = {arXiv}, eprint = {1807.05135}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1807-05135.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1810-09250, author = {Shyam Narayanan and Jelani Nelson}, title = {Optimal terminal dimensionality reduction in Euclidean space}, journal = {CoRR}, volume = {abs/1810.09250}, year = {2018}, url = {http://arxiv.org/abs/1810.09250}, eprinttype = {arXiv}, eprint = {1810.09250}, timestamp = {Wed, 31 Oct 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-1810-09250.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/NelsonY18, author = {Jelani Nelson and Huacheng Yu}, title = {Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR18-129}}, year = {2018}, url = {https://eccc.weizmann.ac.il/report/2018/129}, eprinttype = {ECCC}, eprint = {TR18-129}, timestamp = {Tue, 27 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/NelsonY18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/approx/BlasiokDN17, author = {Jaroslaw Blasiok and Jian Ding and Jelani Nelson}, editor = {Klaus Jansen and Jos{\'{e}} D. P. Rolim and David Williamson and Santosh S. Vempala}, title = {Continuous Monitoring of l{\_}p Norms in Data Streams}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, {APPROX/RANDOM} 2017, August 16-18, 2017, Berkeley, CA, {USA}}, series = {LIPIcs}, volume = {81}, pages = {32:1--32:13}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2017}, url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.32}, doi = {10.4230/LIPICS.APPROX-RANDOM.2017.32}, timestamp = {Tue, 21 Sep 2021 09:36:24 +0200}, biburl = {https://dblp.org/rec/conf/approx/BlasiokDN17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/KapralovNPWWY17, author = {Michael Kapralov and Jelani Nelson and Jakub Pachocki and Zhengyu Wang and David P. Woodruff and Mobin Yahyazadeh}, editor = {Chris Umans}, title = {Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams}, booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS} 2017, Berkeley, CA, USA, October 15-17, 2017}, pages = {475--486}, publisher = {{IEEE} Computer Society}, year = {2017}, url = {https://doi.org/10.1109/FOCS.2017.50}, doi = {10.1109/FOCS.2017.50}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/KapralovNPWWY17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/LarsenN17, author = {Kasper Green Larsen and Jelani Nelson}, editor = {Chris Umans}, title = {Optimality of the Johnson-Lindenstrauss Lemma}, booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS} 2017, Berkeley, CA, USA, October 15-17, 2017}, pages = {633--638}, publisher = {{IEEE} Computer Society}, year = {2017}, url = {https://doi.org/10.1109/FOCS.2017.64}, doi = {10.1109/FOCS.2017.64}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/LarsenN17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/pods/BravermanCINWW17, author = {Vladimir Braverman and Stephen R. Chestnut and Nikita Ivkin and Jelani Nelson and Zhengyu Wang and David P. Woodruff}, editor = {Emanuel Sallinger and Jan Van den Bussche and Floris Geerts}, title = {BPTree: An {\(\mathscr{l}\)}\({}_{\mbox{2}}\) Heavy Hitters Algorithm Using Constant Memory}, booktitle = {Proceedings of the 36th {ACM} {SIGMOD-SIGACT-SIGAI} Symposium on Principles of Database Systems, {PODS} 2017, Chicago, IL, USA, May 14-19, 2017}, pages = {361--376}, publisher = {{ACM}}, year = {2017}, url = {https://doi.org/10.1145/3034786.3034798}, doi = {10.1145/3034786.3034798}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/pods/BravermanCINWW17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/NelsonPW17, author = {Jelani Nelson and Jakub Pachocki and Zhengyu Wang}, title = {Optimal lower bounds for universal relation, samplers, and finding duplicates}, journal = {CoRR}, volume = {abs/1703.08139}, year = {2017}, url = {http://arxiv.org/abs/1703.08139}, eprinttype = {arXiv}, eprint = {1703.08139}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/NelsonPW17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/KapralovNPWWY17, author = {Michael Kapralov and Jelani Nelson and Jakub Pachocki and Zhengyu Wang and David P. Woodruff and Mobin Yahyazadeh}, title = {Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams}, journal = {CoRR}, volume = {abs/1704.00633}, year = {2017}, url = {http://arxiv.org/abs/1704.00633}, eprinttype = {arXiv}, eprint = {1704.00633}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/KapralovNPWWY17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/DingBN17, author = {Jian Ding and Jaroslaw Blasiok and Jelani Nelson}, title = {Continuous monitoring of {\unicode{120001}}\({}_{\mbox{p}}\) norms in data streams}, journal = {CoRR}, volume = {abs/1704.06710}, year = {2017}, url = {http://arxiv.org/abs/1704.06710}, eprinttype = {arXiv}, eprint = {1704.06710}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/DingBN17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1709-09574, author = {Jacob Teo Por Loong and Jelani Nelson and Huacheng Yu}, title = {Fillable arrays with constant time operations and a single bit of redundancy}, journal = {CoRR}, volume = {abs/1709.09574}, year = {2017}, url = {http://arxiv.org/abs/1709.09574}, eprinttype = {arXiv}, eprint = {1709.09574}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1709-09574.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1711-04740, author = {Mark Bun and Jelani Nelson and Uri Stemmer}, title = {Heavy Hitters and the Structure of Local Privacy}, journal = {CoRR}, volume = {abs/1711.04740}, year = {2017}, url = {http://arxiv.org/abs/1711.04740}, eprinttype = {arXiv}, eprint = {1711.04740}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1711-04740.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eatcs/Nelson16, author = {Jelani Nelson}, title = {Chaining introduction with some computer science applications}, journal = {Bull. {EATCS}}, volume = {120}, year = {2016}, url = {http://eatcs.org/beatcs/index.php/beatcs/article/view/450}, timestamp = {Fri, 12 Feb 2021 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/eatcs/Nelson16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/talg/AjtaiFHN16, author = {Mikl{\'{o}}s Ajtai and Vitaly Feldman and Avinatan Hassidim and Jelani Nelson}, title = {Sorting and Selection with Imprecise Comparisons}, journal = {{ACM} Trans. Algorithms}, volume = {12}, number = {2}, pages = {19:1--19:19}, year = {2016}, url = {https://doi.org/10.1145/2701427}, doi = {10.1145/2701427}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/talg/AjtaiFHN16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/LarsenNNT16, author = {Kasper Green Larsen and Jelani Nelson and Huy L. Nguyen and Mikkel Thorup}, editor = {Irit Dinur}, title = {Heavy Hitters via Cluster-Preserving Clustering}, booktitle = {{IEEE} 57th Annual Symposium on Foundations of Computer Science, {FOCS} 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, {USA}}, pages = {61--70}, publisher = {{IEEE} Computer Society}, year = {2016}, url = {https://doi.org/10.1109/FOCS.2016.16}, doi = {10.1109/FOCS.2016.16}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/LarsenNNT16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icalp/CohenNW16, author = {Michael B. Cohen and Jelani Nelson and David P. Woodruff}, editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi}, title = {Optimal Approximate Matrix Product in Terms of Stable Rank}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming, {ICALP} 2016, July 11-15, 2016, Rome, Italy}, series = {LIPIcs}, volume = {55}, pages = {11:1--11:14}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2016}, url = {https://doi.org/10.4230/LIPIcs.ICALP.2016.11}, doi = {10.4230/LIPICS.ICALP.2016.11}, timestamp = {Tue, 11 Feb 2020 15:52:14 +0100}, biburl = {https://dblp.org/rec/conf/icalp/CohenNW16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icalp/BlasiokN16, author = {Jaroslaw Blasiok and Jelani Nelson}, editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi}, title = {An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming, {ICALP} 2016, July 11-15, 2016, Rome, Italy}, series = {LIPIcs}, volume = {55}, pages = {44:1--44:14}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2016}, url = {https://doi.org/10.4230/LIPIcs.ICALP.2016.44}, doi = {10.4230/LIPICS.ICALP.2016.44}, timestamp = {Mon, 05 Feb 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/icalp/BlasiokN16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icalp/LarsenN16, author = {Kasper Green Larsen and Jelani Nelson}, editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi}, title = {The Johnson-Lindenstrauss Lemma Is Optimal for Linear Dimensionality Reduction}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming, {ICALP} 2016, July 11-15, 2016, Rome, Italy}, series = {LIPIcs}, volume = {55}, pages = {82:1--82:11}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2016}, url = {https://doi.org/10.4230/LIPIcs.ICALP.2016.82}, doi = {10.4230/LIPICS.ICALP.2016.82}, timestamp = {Thu, 23 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/icalp/LarsenN16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@incollection{DBLP:reference/algo/Nelson16, author = {Jelani Nelson}, title = {Oblivious Subspace Embeddings}, booktitle = {Encyclopedia of Algorithms}, pages = {1430--1434}, year = {2016}, url = {https://doi.org/10.1007/978-1-4939-2864-4\_795}, doi = {10.1007/978-1-4939-2864-4\_795}, timestamp = {Wed, 12 Jul 2017 01:00:00 +0200}, biburl = {https://dblp.org/rec/reference/algo/Nelson16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/BlasiokN16, author = {Jaroslaw Blasiok and Jelani Nelson}, title = {An improved analysis of the ER-SpUD dictionary learning algorithm}, journal = {CoRR}, volume = {abs/1602.05719}, year = {2016}, url = {http://arxiv.org/abs/1602.05719}, eprinttype = {arXiv}, eprint = {1602.05719}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/BlasiokN16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/BravermanCINWW16, author = {Vladimir Braverman and Stephen R. Chestnut and Nikita Ivkin and Jelani Nelson and Zhengyu Wang and David P. Woodruff}, title = {BPTree: an {\(\mathscr{l}\)}\({}_{\mbox{2}}\) heavy hitters algorithm using constant memory}, journal = {CoRR}, volume = {abs/1603.00759}, year = {2016}, url = {http://arxiv.org/abs/1603.00759}, eprinttype = {arXiv}, eprint = {1603.00759}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/BravermanCINWW16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/LarsenNNT16, author = {Kasper Green Larsen and Jelani Nelson and Huy L. Nguyen and Mikkel Thorup}, title = {Heavy hitters via cluster-preserving clustering}, journal = {CoRR}, volume = {abs/1604.01357}, year = {2016}, url = {http://arxiv.org/abs/1604.01357}, eprinttype = {arXiv}, eprint = {1604.01357}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/LarsenNNT16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/MorganN16, author = {Tom Morgan and Jelani Nelson}, title = {A note on reductions between compressed sensing guarantees}, journal = {CoRR}, volume = {abs/1606.00757}, year = {2016}, url = {http://arxiv.org/abs/1606.00757}, eprinttype = {arXiv}, eprint = {1606.00757}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/MorganN16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/LarsenN16, author = {Kasper Green Larsen and Jelani Nelson}, title = {Optimality of the Johnson-Lindenstrauss Lemma}, journal = {CoRR}, volume = {abs/1609.02094}, year = {2016}, url = {http://arxiv.org/abs/1609.02094}, eprinttype = {arXiv}, eprint = {1609.02094}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/LarsenN16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/BourgainDN15, author = {Jean Bourgain and Sjoerd Dirksen and Jelani Nelson}, editor = {Rocco A. Servedio and Ronitt Rubinfeld}, title = {Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space}, booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015}, pages = {499--508}, publisher = {{ACM}}, year = {2015}, url = {https://doi.org/10.1145/2746539.2746541}, doi = {10.1145/2746539.2746541}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/BourgainDN15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/LarsenNN15, author = {Kasper Green Larsen and Jelani Nelson and Huy L. Nguy{\^{e}}n}, editor = {Rocco A. Servedio and Ronitt Rubinfeld}, title = {Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms}, booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015}, pages = {803--812}, publisher = {{ACM}}, year = {2015}, url = {https://doi.org/10.1145/2746539.2746542}, doi = {10.1145/2746539.2746542}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/LarsenNN15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/AjtaiFHN15, author = {Mikl{\'{o}}s Ajtai and Vitaly Feldman and Avinatan Hassidim and Jelani Nelson}, title = {Sorting and Selection with Imprecise Comparisons}, journal = {CoRR}, volume = {abs/1501.02911}, year = {2015}, url = {http://arxiv.org/abs/1501.02911}, eprinttype = {arXiv}, eprint = {1501.02911}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/AjtaiFHN15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/CohenNW15, author = {Michael B. Cohen and Jelani Nelson and David P. Woodruff}, title = {Optimal approximate matrix product in terms of stable rank}, journal = {CoRR}, volume = {abs/1507.02268}, year = {2015}, url = {http://arxiv.org/abs/1507.02268}, eprinttype = {arXiv}, eprint = {1507.02268}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/CohenNW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/jacm/KaneN14, author = {Daniel M. Kane and Jelani Nelson}, title = {Sparser Johnson-Lindenstrauss Transforms}, journal = {J. {ACM}}, volume = {61}, number = {1}, pages = {4:1--4:23}, year = {2014}, url = {https://doi.org/10.1145/2559902}, doi = {10.1145/2559902}, timestamp = {Wed, 14 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/jacm/KaneN14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icalp/NelsonN14, author = {Jelani Nelson and Huy L. Nguy{\^{e}}n}, editor = {Javier Esparza and Pierre Fraigniaud and Thore Husfeldt and Elias Koutsoupias}, title = {Lower Bounds for Oblivious Subspace Embeddings}, booktitle = {Automata, Languages, and Programming - 41st International Colloquium, {ICALP} 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part {I}}, series = {Lecture Notes in Computer Science}, volume = {8572}, pages = {883--894}, publisher = {Springer}, year = {2014}, url = {https://doi.org/10.1007/978-3-662-43948-7\_73}, doi = {10.1007/978-3-662-43948-7\_73}, timestamp = {Tue, 14 May 2019 10:00:44 +0200}, biburl = {https://dblp.org/rec/conf/icalp/NelsonN14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/soda/NelsonPW14, author = {Jelani Nelson and Eric Price and Mary Wootters}, editor = {Chandra Chekuri}, title = {New constructions of {RIP} matrices with fast multiplication and fewer rows}, booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014}, pages = {1515--1528}, publisher = {{SIAM}}, year = {2014}, url = {https://doi.org/10.1137/1.9781611973402.111}, doi = {10.1137/1.9781611973402.111}, timestamp = {Fri, 22 Apr 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/soda/NelsonPW14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/LarsenNN14, author = {Kasper Green Larsen and Jelani Nelson and Huy L. Nguyen}, title = {Time lower bounds for nonadaptive turnstile streaming algorithms}, journal = {CoRR}, volume = {abs/1407.2151}, year = {2014}, url = {http://arxiv.org/abs/1407.2151}, eprinttype = {arXiv}, eprint = {1407.2151}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/LarsenNN14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/LarsenN14, author = {Kasper Green Larsen and Jelani Nelson}, title = {The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction}, journal = {CoRR}, volume = {abs/1411.2404}, year = {2014}, url = {http://arxiv.org/abs/1411.2404}, eprinttype = {arXiv}, eprint = {1411.2404}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/LarsenN14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/NelsonN13, author = {Jelani Nelson and Huy L. Nguyen}, title = {{OSNAP:} Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings}, booktitle = {54th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS} 2013, 26-29 October, 2013, Berkeley, CA, {USA}}, pages = {117--126}, publisher = {{IEEE} Computer Society}, year = {2013}, url = {https://doi.org/10.1109/FOCS.2013.21}, doi = {10.1109/FOCS.2013.21}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/NelsonN13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/NelsonN13, author = {Jelani Nelson and Huy L. Nguyen}, editor = {Dan Boneh and Tim Roughgarden and Joan Feigenbaum}, title = {Sparsity lower bounds for dimensionality reducing maps}, booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013}, pages = {101--110}, publisher = {{ACM}}, year = {2013}, url = {https://doi.org/10.1145/2488608.2488622}, doi = {10.1145/2488608.2488622}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/NelsonN13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/NelsonN13, author = {Jelani Nelson and Huy L. Nguyen}, title = {Lower bounds for oblivious subspace embeddings}, journal = {CoRR}, volume = {abs/1308.3280}, year = {2013}, url = {http://arxiv.org/abs/1308.3280}, eprinttype = {arXiv}, eprint = {1308.3280}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/NelsonN13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/BourgainN13, author = {Jean Bourgain and Jelani Nelson}, title = {Toward a unified theory of sparse dimensionality reduction in Euclidean space}, journal = {CoRR}, volume = {abs/1311.2542}, year = {2013}, url = {http://arxiv.org/abs/1311.2542}, eprinttype = {arXiv}, eprint = {1311.2542}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/BourgainN13.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/crossroads/Nelson12, author = {Jelani Nelson}, title = {Sketching and streaming algorithms for processing massive data}, journal = {{XRDS}}, volume = {19}, number = {1}, pages = {14--19}, year = {2012}, url = {https://doi.org/10.1145/2331042.2331049}, doi = {10.1145/2331042.2331049}, timestamp = {Fri, 03 Jul 2020 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/crossroads/Nelson12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/approx/NelsonNW12, author = {Jelani Nelson and Huy L. Nguy{\^{e}}n and David P. Woodruff}, editor = {Anupam Gupta and Klaus Jansen and Jos{\'{e}} D. P. Rolim and Rocco A. Servedio}, title = {On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, {APPROX} 2012, and 16th International Workshop, {RANDOM} 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings}, series = {Lecture Notes in Computer Science}, volume = {7408}, pages = {627--638}, publisher = {Springer}, year = {2012}, url = {https://doi.org/10.1007/978-3-642-32512-0\_53}, doi = {10.1007/978-3-642-32512-0\_53}, timestamp = {Sun, 04 Aug 2024 19:37:16 +0200}, biburl = {https://dblp.org/rec/conf/approx/NelsonNW12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/soda/KaneN12, author = {Daniel M. Kane and Jelani Nelson}, editor = {Yuval Rabani}, title = {Sparser Johnson-Lindenstrauss transforms}, booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012}, pages = {1195--1206}, publisher = {{SIAM}}, year = {2012}, url = {https://doi.org/10.1137/1.9781611973099.94}, doi = {10.1137/1.9781611973099.94}, timestamp = {Tue, 02 Feb 2021 17:07:31 +0100}, biburl = {https://dblp.org/rec/conf/soda/KaneN12.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1206-5725, author = {Jelani Nelson and Huy L. Nguy{\^{e}}n and David P. Woodruff}, title = {On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation}, journal = {CoRR}, volume = {abs/1206.5725}, year = {2012}, url = {http://arxiv.org/abs/1206.5725}, eprinttype = {arXiv}, eprint = {1206.5725}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1206-5725.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1211-0986, author = {Jelani Nelson and Eric Price and Mary Wootters}, title = {New constructions of {RIP} matrices with fast multiplication and fewer rows}, journal = {CoRR}, volume = {abs/1211.0986}, year = {2012}, url = {http://arxiv.org/abs/1211.0986}, eprinttype = {arXiv}, eprint = {1211.0986}, timestamp = {Thu, 28 Apr 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1211-0986.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1211-0995, author = {Jelani Nelson and Huy L. Nguyen}, title = {Sparsity Lower Bounds for Dimensionality Reducing Maps}, journal = {CoRR}, volume = {abs/1211.0995}, year = {2012}, url = {http://arxiv.org/abs/1211.0995}, eprinttype = {arXiv}, eprint = {1211.0995}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1211-0995.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1211-1002, author = {Jelani Nelson and Huy L. Nguyen}, title = {{OSNAP:} Faster numerical linear algebra algorithms via sparser subspace embeddings}, journal = {CoRR}, volume = {abs/1211.1002}, year = {2012}, url = {http://arxiv.org/abs/1211.1002}, eprinttype = {arXiv}, eprint = {1211.1002}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1211-1002.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@phdthesis{DBLP:phd/ndltd/Nelson11, author = {Jelani Nelson}, title = {Sketching and streaming algorithms}, school = {Massachusetts Institute of Technology, Cambridge, MA, {USA}}, year = {2011}, url = {https://hdl.handle.net/1721.1/66314}, timestamp = {Wed, 04 May 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/phd/ndltd/Nelson11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/approx/KaneMN11, author = {Daniel Kane and Raghu Meka and Jelani Nelson}, editor = {Leslie Ann Goldberg and Klaus Jansen and R. Ravi and Jos{\'{e}} D. P. Rolim}, title = {Almost Optimal Explicit Johnson-Lindenstrauss Families}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, {APPROX} 2011, and 15th International Workshop, {RANDOM} 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings}, series = {Lecture Notes in Computer Science}, volume = {6845}, pages = {628--639}, publisher = {Springer}, year = {2011}, url = {https://doi.org/10.1007/978-3-642-22935-0\_53}, doi = {10.1007/978-3-642-22935-0\_53}, timestamp = {Thu, 04 Apr 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/approx/KaneMN11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/stoc/KaneNPW11, author = {Daniel M. Kane and Jelani Nelson and Ely Porat and David P. Woodruff}, editor = {Lance Fortnow and Salil P. Vadhan}, title = {Fast moment estimation in data streams in optimal space}, booktitle = {Proceedings of the 43rd {ACM} Symposium on Theory of Computing, {STOC} 2011, San Jose, CA, USA, 6-8 June 2011}, pages = {745--754}, publisher = {{ACM}}, year = {2011}, url = {https://doi.org/10.1145/1993636.1993735}, doi = {10.1145/1993636.1993735}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/stoc/KaneNPW11.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/DiakonikolasKN10, author = {Ilias Diakonikolas and Daniel M. Kane and Jelani Nelson}, title = {Bounded Independence Fools Degree-2 Threshold Functions}, booktitle = {51th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS} 2010, October 23-26, 2010, Las Vegas, Nevada, {USA}}, pages = {11--20}, publisher = {{IEEE} Computer Society}, year = {2010}, url = {https://doi.org/10.1109/FOCS.2010.8}, doi = {10.1109/FOCS.2010.8}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/DiakonikolasKN10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/pods/KaneNW10, author = {Daniel M. Kane and Jelani Nelson and David P. Woodruff}, editor = {Jan Paredaens and Dirk Van Gucht}, title = {An optimal algorithm for the distinct elements problem}, booktitle = {Proceedings of the Twenty-Ninth {ACM} {SIGMOD-SIGACT-SIGART} Symposium on Principles of Database Systems, {PODS} 2010, June 6-11, 2010, Indianapolis, Indiana, {USA}}, pages = {41--52}, publisher = {{ACM}}, year = {2010}, url = {https://doi.org/10.1145/1807085.1807094}, doi = {10.1145/1807085.1807094}, timestamp = {Wed, 14 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/pods/KaneNW10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/pods/NelsonW10, author = {Jelani Nelson and David P. Woodruff}, editor = {Jan Paredaens and Dirk Van Gucht}, title = {Fast Manhattan sketches in data streams}, booktitle = {Proceedings of the Twenty-Ninth {ACM} {SIGMOD-SIGACT-SIGART} Symposium on Principles of Database Systems, {PODS} 2010, June 6-11, 2010, Indianapolis, Indiana, {USA}}, pages = {99--110}, publisher = {{ACM}}, year = {2010}, url = {https://doi.org/10.1145/1807085.1807101}, doi = {10.1145/1807085.1807101}, timestamp = {Tue, 06 Nov 2018 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/pods/NelsonW10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/soda/KaneNW10, author = {Daniel M. Kane and Jelani Nelson and David P. Woodruff}, editor = {Moses Charikar}, title = {On the Exact Space Complexity of Sketching and Streaming Small Norms}, booktitle = {Proceedings of the Twenty-First Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2010, Austin, Texas, USA, January 17-19, 2010}, pages = {1161--1178}, publisher = {{SIAM}}, year = {2010}, url = {https://doi.org/10.1137/1.9781611973075.93}, doi = {10.1137/1.9781611973075.93}, timestamp = {Tue, 02 Feb 2021 17:07:39 +0100}, biburl = {https://dblp.org/rec/conf/soda/KaneNW10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1006-3585, author = {Daniel M. Kane and Jelani Nelson}, title = {A Derandomized Sparse Johnson-Lindenstrauss Transform}, journal = {CoRR}, volume = {abs/1006.3585}, year = {2010}, url = {http://arxiv.org/abs/1006.3585}, eprinttype = {arXiv}, eprint = {1006.3585}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1006-3585.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1007-4191, author = {Daniel M. Kane and Jelani Nelson and Ely Porat and David P. Woodruff}, title = {Fast Moment Estimation in Data Streams in Optimal Space}, journal = {CoRR}, volume = {abs/1007.4191}, year = {2010}, url = {http://arxiv.org/abs/1007.4191}, eprinttype = {arXiv}, eprint = {1007.4191}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1007-4191.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-1012-1577, author = {Daniel M. Kane and Jelani Nelson}, title = {A Sparser Johnson-Lindenstrauss Transform}, journal = {CoRR}, volume = {abs/1012.1577}, year = {2010}, url = {http://arxiv.org/abs/1012.1577}, eprinttype = {arXiv}, eprint = {1012.1577}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-1012-1577.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/KaneMN10, author = {Daniel Kane and Raghu Meka and Jelani Nelson}, title = {Almost Optimal Explicit Johnson-Lindenstrauss Transformations}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR10-183}}, year = {2010}, url = {https://eccc.weizmann.ac.il/report/2010/183}, eprinttype = {ECCC}, eprint = {TR10-183}, timestamp = {Thu, 04 Apr 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/KaneMN10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/KaneN10, author = {Daniel M. Kane and Jelani Nelson}, title = {A Derandomized Sparse Johnson-Lindenstrauss Transform}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR10-098}}, year = {2010}, url = {https://eccc.weizmann.ac.il/report/2010/098}, eprinttype = {ECCC}, eprint = {TR10-098}, timestamp = {Tue, 27 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/KaneN10.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/comgeo/AbbottBCDDHKLNRSY09, author = {Timothy G. Abbott and Michael A. Burr and Timothy M. Chan and Erik D. Demaine and Martin L. Demaine and John Hugg and Daniel Kane and Stefan Langerman and Jelani Nelson and Eynat Rafalin and Kathryn Seyboth and Vincent Yeung}, title = {Dynamic ham-sandwich cuts in the plane}, journal = {Comput. Geom.}, volume = {42}, number = {5}, pages = {419--428}, year = {2009}, url = {https://doi.org/10.1016/j.comgeo.2008.09.008}, doi = {10.1016/J.COMGEO.2008.09.008}, timestamp = {Thu, 04 Apr 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/comgeo/AbbottBCDDHKLNRSY09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/icalp/AjtaiFHN09, author = {Mikl{\'{o}}s Ajtai and Vitaly Feldman and Avinatan Hassidim and Jelani Nelson}, editor = {Susanne Albers and Alberto Marchetti{-}Spaccamela and Yossi Matias and Sotiris E. Nikoletseas and Wolfgang Thomas}, title = {Sorting and Selection with Imprecise Comparisons}, booktitle = {Automata, Languages and Programming, 36th International Colloquium, {ICALP} 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part {I}}, series = {Lecture Notes in Computer Science}, volume = {5555}, pages = {37--48}, publisher = {Springer}, year = {2009}, url = {https://doi.org/10.1007/978-3-642-02927-1\_5}, doi = {10.1007/978-3-642-02927-1\_5}, timestamp = {Tue, 14 May 2019 10:00:44 +0200}, biburl = {https://dblp.org/rec/conf/icalp/AjtaiFHN09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-0904-2027, author = {Jelani Nelson and David P. Woodruff}, title = {A Near-Optimal Algorithm for L1-Difference}, journal = {CoRR}, volume = {abs/0904.2027}, year = {2009}, url = {http://arxiv.org/abs/0904.2027}, eprinttype = {arXiv}, eprint = {0904.2027}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-0904-2027.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-0911-3389, author = {Ilias Diakonikolas and Daniel M. Kane and Jelani Nelson}, title = {Bounded Independence Fools Degree-2 Threshold Functions}, journal = {CoRR}, volume = {abs/0911.3389}, year = {2009}, url = {http://arxiv.org/abs/0911.3389}, eprinttype = {arXiv}, eprint = {0911.3389}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-0911-3389.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/DiakonikolasKN09, author = {Ilias Diakonikolas and Daniel M. Kane and Jelani Nelson}, title = {Bounded Independence Fools Degree-2 Threshold Functions}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR09-117}}, year = {2009}, url = {https://eccc.weizmann.ac.il/report/2009/117}, eprinttype = {ECCC}, eprint = {TR09-117}, timestamp = {Tue, 27 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/DiakonikolasKN09.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/HarveyNO08, author = {Nicholas J. A. Harvey and Jelani Nelson and Krzysztof Onak}, title = {Sketching and Streaming Entropy via Approximation Theory}, booktitle = {49th Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS} 2008, October 25-28, 2008, Philadelphia, PA, {USA}}, pages = {489--498}, publisher = {{IEEE} Computer Society}, year = {2008}, url = {https://doi.org/10.1109/FOCS.2008.76}, doi = {10.1109/FOCS.2008.76}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/HarveyNO08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/itw/HarveyNO08, author = {Nicholas J. A. Harvey and Jelani Nelson and Krzysztof Onak}, title = {Streaming algorithms for estimating entropy}, booktitle = {2008 {IEEE} Information Theory Workshop, {ITW} 2008, Porto, Portugal, May 5-9, 2008}, pages = {227--231}, publisher = {{IEEE}}, year = {2008}, url = {https://doi.org/10.1109/ITW.2008.4578656}, doi = {10.1109/ITW.2008.4578656}, timestamp = {Mon, 09 Aug 2021 14:54:02 +0200}, biburl = {https://dblp.org/rec/conf/itw/HarveyNO08.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-0804-4138, author = {Nicholas J. A. Harvey and Jelani Nelson and Krzysztof Onak}, title = {Sketching and Streaming Entropy via Approximation Theory}, journal = {CoRR}, volume = {abs/0804.4138}, year = {2008}, url = {http://arxiv.org/abs/0804.4138}, eprinttype = {arXiv}, eprint = {0804.4138}, timestamp = {Mon, 13 Aug 2018 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/corr/abs-0804-4138.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/corr/abs-0811-3648, author = {Daniel M. Kane and Jelani Nelson and David P. Woodruff}, title = {Revisiting Norm Estimation in Data Streams}, journal = {CoRR}, volume = {abs/0811.3648}, year = {2008}, url = {http://arxiv.org/abs/0811.3648}, eprinttype = {arXiv}, eprint = {0811.3648}, timestamp = {Thu, 03 Mar 2022 00:00:00 +0100}, biburl = {https://dblp.org/rec/journals/corr/abs-0811-3648.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/spaa/BenderFFFKN07, author = {Michael A. Bender and Martin Farach{-}Colton and Jeremy T. Fineman and Yonatan R. Fogel and Bradley C. Kuszmaul and Jelani Nelson}, editor = {Phillip B. Gibbons and Christian Scheideler}, title = {Cache-oblivious streaming B-trees}, booktitle = {{SPAA} 2007: Proceedings of the 19th Annual {ACM} Symposium on Parallelism in Algorithms and Architectures, San Diego, California, USA, June 9-11, 2007}, pages = {81--92}, publisher = {{ACM}}, year = {2007}, url = {https://doi.org/10.1145/1248377.1248393}, doi = {10.1145/1248377.1248393}, timestamp = {Fri, 09 Apr 2021 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/spaa/BenderFFFKN07.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@article{DBLP:journals/eccc/Nelson07, author = {Jelani Nelson}, title = {A Note on Set Cover Inapproximability Independent of Universe Size}, journal = {Electron. Colloquium Comput. Complex.}, volume = {{TR07-105}}, year = {2007}, url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-105/index.html}, eprinttype = {ECCC}, eprint = {TR07-105}, timestamp = {Wed, 28 Sep 2022 01:00:00 +0200}, biburl = {https://dblp.org/rec/journals/eccc/Nelson07.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/cccg/AbbottDDKLNY05, author = {Timothy G. Abbott and Erik D. Demaine and Martin L. Demaine and Daniel Kane and Stefan Langerman and Jelani Nelson and Vincent Yeung}, title = {Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane}, booktitle = {Proceedings of the 17th Canadian Conference on Computational Geometry, CCCG'05, University of Windsor, Ontario, Canada, August 10-12, 2005}, pages = {61--64}, year = {2005}, url = {http://www.cccg.ca/proceedings/2005/79.pdf}, timestamp = {Thu, 04 Apr 2024 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/cccg/AbbottDDKLNY05.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.