N. Menand, E. Waingarten. Streaming and Massively Parallel Algorithms for Euclidean Max-Cut. (ARXIV)
Y. Bao, A. Baweja, N. Menand, E. Waingarten, N. White, T. Zhang. Average-Distortion Sketching. (ARXIV)
D. Chakrabarty, X. Chen, S. Ristic, C. Seshadhri, E. Waingarten. Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning. 57th ACM Symposium on Theory of Computing, (STOC) 2025. (ARXIV)
Y. Bao, S. Kannan, E. Waingarten, Nearly Tight Bounds on Testing of Metric Properties. 36th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025. (ARXIV)
X. Chen, A. De, S. Nadimpalli, R. Servedio, E. Waingarten, Lower Bounds for Convexity Testing. 36th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025. (ARXIV)
M. Charikar and E. Waingarten. The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction. Proceedings of 36th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2025 (ARXIV) My talk here
R. Jayaram, E. Waingarten, T. Zhang. Data-Dependent LSH for the Earth Mover's Distance. 56th ACM Symposium on Theory of Computing, (STOC) 2024. (ARXIV) My talk here.
M. Charikar, M. Kapralov, E. Waingarten. A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. Proceedings of 35th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024. (ARXIV)
M. Charikar, M. Henzinger, L. Hu, M. Votsch, E. Waingarten. Simple, Scalable, and Effective Clustering via One-dimensional Projections. 33rd Annual Conference on Advances in Neural Information Processing Systems, (NeurIPS) 2023. (ARXIV)
A. Bakshi, P. Indyk, R. Jayaram, S. Silwal, and E. Waingarten. A Near-Linear Time Algorithm for the Chamfer Distance. 33rd Annual Conference on Advances in Neural Information Processing Systems, (NeurIPS) 2023. (ARXIV)
M. Charikar, B. Chen, C. Re, and Erik Waingarten. Fast Algorithms for a New Relaxation of Optimal Transport. 36th Conference on Learning Theory, (COLT) 2023. (ARXIV)
V. Cohen-Addad, X. Chen, R. Jayaram, and E. Waingarten. Streaming Euclidean MST to a Constant Factor. 55th ACM Symposium on Theory of Computing, (STOC) 2023. (ARXIV)
M. Aliakbarpour, A. McGregor, J. Nelson, and E. Waingarten. Estimation of Entropy in Constant Space with Improved Sample Complexity. Proceedings of the 32nd Annual Conference on Advances in Neural Information Processing Systems, (NeurIPS) 2022. (ARXIV)
M. Charikar and E. Waingarten. Polylogarithmic Sketches for Clustering. Proceedings of the 50th International Colloquium on Automata, Languages and Programming, (ICALP) 2022. (ARXIV)
O. Ben-Eliezer, S. Letzter, and E. Waingarten. Finding Monotone Patterns in Sublinear Time, Adaptively. Proceedings of the 50th International Colloquium on Automata, Languages and Programming, (ICALP) 2022. (ARXIV)
X. Chen, R. Jayaram, A. Levi, and E. Waingarten. New Streaming Algorithms for High-Dimensional MST and EMD. 54th ACM Symposium on Theory of Computing, (STOC) 2022. (HERE). Rajesh's Talk at CMU.
X. Chen, R. Jayaram, A. Levi, E. Waingarten. Learning and Testing Junta Distributions with Subcube Conditioning. 32nd Annual Conference on Learning Theory (COLT) 2021. (ARXIV).
A. Andoni, A. Nikolov, I. Razenshteyn, and E. Waingarten. Approximate Nearest Neighbors Beyond Space Partitions. Proceedings of 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021. (HERE). My SODA Talk.
C. Canonne, X. Chen, A. Levi, G. Kamath, and E. Waingarten. Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. Proceedings of 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021. (ARXIV) My WOLA talk here.
R. K. Pallavoor, S. Raskhodnikova, and E. Waingarten. Approximating the Distance to Monotonicity of Boolean Functions. Proceedings of 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020. (ARXIV)
X. Chen, A. Levi, and E. Waingarten. Nearly Optimal Edge Estimation with Independent Set Queries. Proceedings of 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020. (ARXIV)
O. Ben-Eliezer, C. Canonne, S. Letzter, and E. Waingarten. Finding Monotone Patterns in Sublinear Time. 60th IEEE Symposium on Foundations of Computer Science, (FOCS) 2019. (ARXIV)
X. Chen and E. Waingarten. Testing Unateness Nearly Optimally. 51st ACM Symposium on Theory of Computing, (STOC) 2019. (ARXIV)
J. Li, A. Nikolov, I. Razenshteyn, and E. Waingarten. On Mean Estimation for General Norms with Statistical Queries. 30th Annual Conference on Learning Theory (COLT) 2019. (ARXIV)
A. Levi and E. Waingarten. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. Proceedings of the 2019 ACM Conference on Innovations in Theoretical Computer Science (ITCS) 2019. (ARXIV)
A. Andoni, A. Naor, A. Nikolov, I. Razenshteyn, and E. Waingarten. Holder Homeomorphism and Approximate Nearest Neighbors. 59th IEEE Symposium on Foundations of Computer Science, (FOCS) 2018. (HERE) Covered here, and here.
A. Andoni, A. Naor, A. Nikolov, I. Razenshteyn, and E. Waingarten. Data-Dependent Hashing via Nonlinear Spectral Gaps. 50th ACM Symposium on Theory of Computing, (STOC) 2018. (HERE)
X. Chen, E. Waingarten and J. Xie. Boolean Unateness Testing with ~O(n^{3/4}) Adaptive Queries. 58th IEEE Symposium on Foundations of Computer Science, (FOCS) 2017. (ARXIV) My talk here.
X. Chen, R. A. Servedio, L.Y. Tan and E. Waingarten, Adaptivity is Exponentially Powerful for Testing Monotonicity of Halfspaces. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, (APPROX/RANDOM) 2017. (ARXIV)
X. Chen, R. A. Servedio, L.Y. Tan, E. Waingarten, and J. Xie, Settling the Query Complexity of Non-adaptive Junta Testing. 32nd Conference on Computational Complexity (CCC) 2017. Best paper award at CCC 2017. Invited to the Journal of the ACM. (ECCC, ARXIV) Covered here. My talk on TCS+.
X. Chen, E. Waingarten, J. Xie, Beyond Talagrand: New Lower Bounds for Testing Monotonicity and Unateness. proceedings of the 49th ACM Symposium on Theory of Computing (STOC), 2017. (ARXIV)
A. Andoni, H. Nguyen, A. Nikolov, I. Razenshteyn, E. Waingarten, Approximate Near Neighbors for General Symmetric Norms. proceedings of the 49th ACM Symposium on Theory of Computing (STOC), 2017. (ARXIV)
A.Andoni, T.Laarhoven, I.Razenshteyn and E.Waingarten, Optimal Hashing-based Time– Space Trade-offs for Approximate Near Neighbors, proceedings of 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017.(ARXIV)
E.D. Demaine, V. Ganesan, V. Kontsevoi, Q. Liu, Q. Liu, F. Ma, O. Nachum, A. Sidford, E. Waingarten, D. Ziegler. Arboral Satisfaction: Recognition and LP Approximation, Information Processing Letters. 2017.
E.D.Demaine, F.Ma, A.Schvartzman, E.Waingarten, S.Aaronson,The Fewest Clues Problem, proceedings of the 8th International Conference on Fun with Algorithms (FUN), 2016. Invited to special issue of Theoretical Computer Science. (HERE)
J. Bosboom, E.D. Demaine, A. Hesterberg, J. Lynch, E. Waingarten, Mario Kart is Hard. in Abstracts from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG), 2015. (HERE)
E.D. Demaine, F. Ma, M. Susskind, E. Waingarten, You Should be Scared of German Ghost, in Journal of Information Processing, volume 23, number 3, 2015. (HERE)
E.D. Demaine, F.Ma, E.Waingarten, Playing Dominoes is Hard, Except by Yourself, proceedings of the 7th International Conference on Fun with Algorithms (FUN), 2014. (HERE)