Erik Waingarten

Orcid: 0000-0003-0097-7981

Affiliations:
  • University of Pennsylvania, USA


According to our database1, Erik Waingarten authored at least 38 papers between 2014 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Data-Dependent LSH for the Earth Mover's Distance.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023
Streaming Euclidean MST to a Constant Factor.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Simple, Scalable and Effective Clustering via One-Dimensional Projections.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Near-Linear Time Algorithm for the Chamfer Distance.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Fast Algorithms for a New Relaxation of Optimal Transport.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022
The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction.
CoRR, 2022

New streaming algorithms for high dimensional EMD and MST.
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Estimation of Entropy in Constant Space with Improved Sample Complexity.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Polylogarithmic Sketches for Clustering.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Finding Monotone Patterns in Sublinear Time, Adaptively.
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021
Approximate Nearest Neighbors Beyond Space Partitions.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Learning and testing junta distributions with sub cube conditioning.
Proceedings of the Conference on Learning Theory, 2021

2020
New Methods in Sublinear Computation for High Dimensional Problems.
PhD thesis, 2020

Learning and Testing Junta Distributions with Subcube Conditioning.
CoRR, 2020

Nearly optimal edge estimation with independent set queries.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Approximating the Distance to Monotonicity of Boolean Functions.
Electron. Colloquium Comput. Complex., 2019

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning.
Electron. Colloquium Comput. Complex., 2019

Finding monotone patterns in sublinear time.
Electron. Colloquium Comput. Complex., 2019

Optimal Adaptive Detection of Monotone Patterns.
CoRR, 2019

Testing unateness nearly optimally.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

On Mean Estimation for General Norms with Statistical Queries.
Proceedings of the Conference on Learning Theory, 2019

2018
The fewest clues problem.
Theor. Comput. Sci., 2018

Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs.
Electron. Colloquium Comput. Complex., 2018

Data-dependent hashing via nonlinear spectral gaps.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Hölder Homeomorphisms and Approximate Nearest Neighbors.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Arboral satisfaction: Recognition and LP approximation.
Inf. Process. Lett., 2017

Settling the query complexity of non-adaptive junta testing.
Electron. Colloquium Comput. Complex., 2017

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Approximate near neighbors for general symmetric norms.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Boolean Unateness Testing with Õ(n<sup>3/4</sup>) Adaptive Queries.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.
Proceedings of the Approximation, 2017

2016
Approximate Near Neighbors for General Symmetric Norms.
CoRR, 2016

Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors.
CoRR, 2016

2015
You Should Be Scared of German Ghost.
J. Inf. Process., 2015

Mario Kart Is Hard.
Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

2014
Playing Dominoes Is Hard, Except by Yourself.
Proceedings of the Fun with Algorithms - 7th International Conference, 2014


  Loading...