Erik Waingarten

Publication Activity (10 Years)

Years Active: 2014-2024
Publications (10 Years): 63

Top Topics

Nearest Neighbor

Sample Complexity

Prime Implicants

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Moses Charikar, Michael Kapralov, Erik Waingarten
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. CoRR (2024)
Moses Charikar, Michael Kapralov, Erik Waingarten
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. SODA (2024)
Rajesh Jayaram, Erik Waingarten, Tian Zhang
Data-Dependent LSH for the Earth Mover's Distance. CoRR (2024)
Rajesh Jayaram, Erik Waingarten, Tian Zhang
Data-Dependent LSH for the Earth Mover's Distance. STOC (2024)
Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, Erik Waingarten
Near-Linear Time Algorithm for the Chamfer Distance. NeurIPS (2023)
Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, Erik Waingarten
A Near-Linear Time Algorithm for the Chamfer Distance. CoRR (2023)
Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten
Fast Algorithms for a New Relaxation of Optimal Transport. CoRR (2023)
Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten
Fast Algorithms for a New Relaxation of Optimal Transport. COLT (2023)
Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, Erik Waingarten
Simple, Scalable and Effective Clustering via One-Dimensional Projections. NeurIPS (2023)
Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, Erik Waingarten
Simple, Scalable and Effective Clustering via One-Dimensional Projections. CoRR (2023)
Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, Erik Waingarten
Streaming Euclidean MST to a Constant Factor. STOC (2023)
Moses Charikar, Erik Waingarten
The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction. CoRR (2022)
Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
Estimation of Entropy in Constant Space with Improved Sample Complexity. CoRR (2022)
Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
Estimation of Entropy in Constant Space with Improved Sample Complexity. NeurIPS (2022)
Moses Charikar, Erik Waingarten
Polylogarithmic Sketches for Clustering. CoRR (2022)
Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten
Finding Monotone Patterns in Sublinear Time, Adaptively. ICALP (2022)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
Approximating the distance to monotonicity of Boolean functions. Random Struct. Algorithms 60 (2) (2022)
Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
Streaming Euclidean MST to a Constant Factor. CoRR (2022)
Moses Charikar, Erik Waingarten
Polylogarithmic Sketches for Clustering. ICALP (2022)
Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
New streaming algorithms for high dimensional EMD and MST. STOC (2022)
Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
Learning and testing junta distributions with sub cube conditioning. COLT (2021)
Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
New Streaming Algorithms for High Dimensional EMD and MST. CoRR (2021)
Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Approximate Nearest Neighbors Beyond Space Partitions. SODA (2021)
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning. SODA (2021)
Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
Learning and Testing Junta Distributions with Subcube Conditioning. CoRR (2020)
Xi Chen, Amit Levi, Erik Waingarten
Nearly optimal edge estimation with independent set queries. SODA (2020)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
Approximating the Distance to Monotonicity of Boolean Functions. SODA (2020)
Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten
Finding monotone patterns in sublinear time. CoRR (2019)
Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten
Finding Monotone Patterns in Sublinear Time. FOCS (2019)
Xi Chen, Erik Waingarten
Testing Unateness Nearly Optimally. CoRR (2019)
Xi Chen, Erik Waingarten
Testing unateness nearly optimally. STOC (2019)
Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten
Finding monotone patterns in sublinear time. Electron. Colloquium Comput. Complex. 26 (2019)
Xi Chen, Amit Levi, Erik Waingarten
Nearly optimal edge estimation with independent set queries. CoRR (2019)
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. CoRR (2019)
Jerry Li, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
On Mean Estimation for General Norms with Statistical Queries. COLT (2019)
Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten
Optimal Adaptive Detection of Monotone Patterns. CoRR (2019)
Jerry Li, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
On Mean Estimation for General Norms with Statistical Queries. CoRR (2019)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
Approximating the Distance to Monotonicity of Boolean Functions. CoRR (2019)
Amit Levi, Erik Waingarten
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. ITCS (2019)
Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. Electron. Colloquium Comput. Complex. 26 (2019)
Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
Approximating the Distance to Monotonicity of Boolean Functions. Electron. Colloquium Comput. Complex. 26 (2019)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the Query Complexity of Non-adaptive Junta Testing. J. ACM 65 (6) (2018)
Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson
The fewest clues problem. Theor. Comput. Sci. 748 (2018)
Amit Levi, Erik Waingarten
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. CoRR (2018)
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Data-dependent hashing via nonlinear spectral gaps. STOC (2018)
Amit Levi, Erik Waingarten
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. Electron. Colloquium Comput. Complex. 25 (2018)
Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Hölder Homeomorphisms and Approximate Nearest Neighbors. FOCS (2018)
Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. SODA (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the query complexity of non-adaptive junta testing. CoRR (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the query complexity of non-adaptive junta testing. Electron. Colloquium Comput. Complex. 24 (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the Query Complexity of Non-Adaptive Junta Testing. Computational Complexity Conference (2017)
Xi Chen, Erik Waingarten, Jinyu Xie
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. STOC (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
Adaptivity is exponentially powerful for testing monotonicity of halfspaces. CoRR (2017)
Xi Chen, Erik Waingarten, Jinyu Xie
) Adaptive Queries. FOCS (2017)
Xi Chen, Erik Waingarten, Jinyu Xie
Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness. CoRR (2017)
Xi Chen, Erik Waingarten, Jinyu Xie
) Adaptive Queries. CoRR (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. APPROX-RANDOM (2017)
Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Approximate near neighbors for general symmetric norms. STOC (2017)
Erik D. Demaine, Varun Ganesan, Vladislav Kontsevoi, Qipeng Liu, Quanquan C. Liu, Fermi Ma, Ofir Nachum, Aaron Sidford, Erik Waingarten, Daniel Ziegler
Arboral satisfaction: Recognition and LP approximation. Inf. Process. Lett. 127 (2017)
Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson
The Fewest Clues Problem. FUN (2016)
Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
Approximate Near Neighbors for General Symmetric Norms. CoRR (2016)
Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. CoRR (2016)
Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors. CoRR (2016)
Erik D. Demaine, Fermi Ma, Matthew Susskind, Erik Waingarten
You Should Be Scared of German Ghost. J. Inf. Process. 23 (3) (2015)
Jeffrey Bosboom, Erik D. Demaine, Adam Hesterberg, Jayson Lynch, Erik Waingarten
Mario Kart Is Hard. JCDCGG (2015)
Erik D. Demaine, Fermi Ma, Erik Waingarten
Playing Dominoes Is Hard, Except by Yourself. FUN (2014)