Sotabase

Career

· PhD Student, Columbia University
· Postdoctoral Researcher, Stanford University
· Assistant Professor, University of Pennsylvania

Publications (41)

Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
ACM-SIAM Symposium on Discrete Algorithms · 2016
135
cited
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
Symposium on the Theory of Computing · 2017
46
cited
Approximate near neighbors for general symmetric norms
Symposium on the Theory of Computing · 2016
40
cited
Data-dependent hashing via nonlinear spectral gaps
Symposium on the Theory of Computing · 2018
40
cited
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
Electron. Colloquium Comput. Complex. · 2019
37
cited
Approximating the distance to monotonicity of Boolean functions
Electron. Colloquium Comput. Complex. · 2019
35
cited
Settling the Query Complexity of Non-adaptive Junta Testing
Cybersecurity and Cyberforensics Conference · 2017
33
cited
Learning and Testing Junta Distributions with Subcube Conditioning
Annual Conference Computational Learning Theory · 2020
32
cited
Hölder Homeomorphisms and Approximate Nearest Neighbors
IEEE Annual Symposium on Foundations of Computer Science · 2018
31
cited
New streaming algorithms for high dimensional EMD and MST
Symposium on the Theory of Computing · 2021
26
cited
Nearly optimal edge estimation with independent set queries
ACM-SIAM Symposium on Discrete Algorithms · 2019
24
cited
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs
Electron. Colloquium Comput. Complex. · 2018
19
cited
A Near-Linear Time Algorithm for the Chamfer Distance
arXiv.org · 2023
17
cited
Boolean Unateness Testing with Õ(n^{3/4}) Adaptive Queries
IEEE Annual Symposium on Foundations of Computer Science · 2017
17
cited
The Fewest Clues Problem
Fun with Algorithms · 2016
14
cited
The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction
ACM-SIAM Symposium on Discrete Algorithms · 2022
14
cited
Finding Monotone Patterns in Sublinear Time
IEEE Annual Symposium on Foundations of Computer Science · 2019
11
cited
Streaming Euclidean MST to a Constant Factor
Symposium on the Theory of Computing · 2022
11
cited
On Mean Estimation for General Norms with Statistical Queries
Annual Conference Computational Learning Theory · 2019
9
cited
Approximate Nearest Neighbors Beyond Space Partitions
ACM-SIAM Symposium on Discrete Algorithms · 2021
8
cited
Sotabase
Erik Waingarten | Researcher Profile | Sotabase | Sotabase