Sotabase

Career

· Department Chair, Electrical Engineering and Computer Sciences, University of California, Berkeley2025–
· Visiting Scientist and Program Organizer, UC Berkeley, Simons Institute for the Theory of Computing (SITC)2020–
· Professor, Department of EECS, UC Berkeley2019–
· Professor of Electrical Engineering and Computer Sciences, University of California, Berkeley2019–
· Researcher, Center for the Theoretical Foundations of Learning, Inference, Information, Intelligence, Mathematics and Microeconomics at Berkeley (CLIMB)

Publications (94)

OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings
IEEE Annual Symposium on Foundations of Computer Science · 2012
402
cited
Sparser Johnson-Lindenstrauss Transforms
ACM-SIAM Symposium on Discrete Algorithms · 2010
382
cited
An optimal algorithm for the distinct elements problem
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems · 2010
367
cited
On the exact space complexity of sketching and streaming small norms
ACM-SIAM Symposium on Discrete Algorithms · 2010
176
cited
Optimality of the Johnson-Lindenstrauss Lemma
IEEE Annual Symposium on Foundations of Computer Science · 2016
166
cited
Cache-oblivious streaming B-trees
ACM Symposium on Parallelism in Algorithms and Architectures · 2007
162
cited
Heavy Hitters and the Structure of Local Privacy
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems · 2017
160
cited
Optimal Approximate Matrix Product in Terms of Stable Rank
International Colloquium on Automata, Languages and Programming · 2015
143
cited
Toward a unified theory of sparse dimensionality reduction in Euclidean space
Symposium on the Theory of Computing · 2013
131
cited
Bounded Independence Fools Degree-2 Threshold Functions
IEEE Annual Symposium on Foundations of Computer Science · 2009
113
cited
Sketching and Streaming Entropy via Approximation Theory
2008 49th Annual IEEE Symposium on Foundations of Computer Science · 2008
113
cited
Fast moment estimation in data streams in optimal space
Symposium on the Theory of Computing · 2010
98
cited
Heavy Hitters via Cluster-Preserving Clustering
IEEE Annual Symposium on Foundations of Computer Science · 2016
85
cited
The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
International Colloquium on Automata, Languages and Programming · 2014
77
cited
Sorting and Selection with Imprecise Comparisons
International Colloquium on Automata, Languages and Programming · 2009
72
cited
Almost Optimal Explicit Johnson-Lindenstrauss Families
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques · 2011
64
cited
A Derandomized Sparse Johnson-Lindenstrauss Transform
Electron. Colloquium Comput. Complex. · 2010
62
cited
BPTree: An ℓ2 Heavy Hitters Algorithm Using Constant Memory
ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems · 2016
62
cited
Sparsity lower bounds for dimensionality reducing maps
Symposium on the Theory of Computing · 2012
59
cited
Lower Bounds for Oblivious Subspace Embeddings
International Colloquium on Automata, Languages and Programming · 2013
56
cited
Sotabase
Jelani Nelson | Researcher Profile | Sotabase | Sotabase