Erik Waingarten

According to our database, Erik Waingarten authored at least 39 papers between 2014 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Lower Bounds for Convexity Testing.

Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten

CoRR, 2024

Data-Dependent LSH for the Earth Mover's Distance.

Rajesh Jayaram, Erik Waingarten, Tian Zhang

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations.

Moses Charikar, Michael Kapralov, Erik Waingarten

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Streaming Euclidean MST to a Constant Factor.

Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, Erik Waingarten

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Simple, Scalable and Effective Clustering via One-Dimensional Projections.

Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, Erik Waingarten

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.

Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, Erik Waingarten

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.

Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten

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.

Moses Charikar, Erik Waingarten

CoRR, 2022

New streaming algorithms for high dimensional EMD and MST.

Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten

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.

Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Polylogarithmic Sketches for Clustering.

Moses Charikar, Erik Waingarten

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Finding Monotone Patterns in Sublinear Time, Adaptively.

Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Approximate Nearest Neighbors Beyond Space Partitions.

Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Learning and testing junta distributions with sub cube conditioning.

Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten

Proceedings of the Conference on Learning Theory, 2021

2020

New Methods in Sublinear Computation for High Dimensional Problems.

Erik Alex Waingarten

PhD thesis, 2020

Learning and Testing Junta Distributions with Subcube Conditioning.

Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten

CoRR, 2020

Nearly optimal edge estimation with independent set queries.

Xi Chen, Amit Levi, Erik Waingarten

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Approximating the Distance to Monotonicity of Boolean Functions.

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten

Electron. Colloquium Comput. Complex., 2019

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning.

Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten

Electron. Colloquium Comput. Complex., 2019

Finding monotone patterns in sublinear time.

Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten

Electron. Colloquium Comput. Complex., 2019

Optimal Adaptive Detection of Monotone Patterns.

Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten

CoRR, 2019

Testing unateness nearly optimally.

Xi Chen, Erik Waingarten

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

On Mean Estimation for General Norms with Statistical Queries.

Jerry Li, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the Conference on Learning Theory, 2019

2018

The fewest clues problem.

Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson

Theor. Comput. Sci., 2018

Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs.

Amit Levi, Erik Waingarten

Electron. Colloquium Comput. Complex., 2018

Data-dependent hashing via nonlinear spectral gaps.

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Hölder Homeomorphisms and Approximate Nearest Neighbors.

Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Arboral satisfaction: Recognition and LP approximation.

Erik D. Demaine, Varun Ganesan, Vladislav Kontsevoi, Qipeng Liu, Quanquan C. Liu, Fermi Ma, Ofir Nachum, Aaron Sidford, Erik Waingarten, Daniel Ziegler

Inf. Process. Lett., 2017

Settling the query complexity of non-adaptive junta testing.

Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie

Electron. Colloquium Comput. Complex., 2017

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness.

Xi Chen, Erik Waingarten, Jinyu Xie

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Approximate near neighbors for general symmetric norms.

Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors.

Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Boolean Unateness Testing with Õ(n^3/4) Adaptive Queries.

Xi Chen, Erik Waingarten, Jinyu Xie

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.

Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten

Proceedings of the Approximation, 2017

2016

Approximate Near Neighbors for General Symmetric Norms.

Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten

CoRR, 2016

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

Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten

CoRR, 2016

2015

You Should Be Scared of German Ghost.

Erik D. Demaine, Fermi Ma, Matthew Susskind, Erik Waingarten

J. Inf. Process., 2015

Mario Kart Is Hard.

Jeffrey Bosboom, Erik D. Demaine, Adam Hesterberg, Jayson Lynch, Erik Waingarten

Proceedings of the Discrete and Computational Geometry and Graphs - 18th Japan Conference, 2015

2014

Playing Dominoes Is Hard, Except by Yourself.

Erik D. Demaine, Fermi Ma, Erik Waingarten

Proceedings of the Fun with Algorithms - 7th International Conference, 2014