Erik Waingarten

88 papers A* 35A 2Misc 2Journal 47Unranked 2

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Prune, Don't Rebuild: Efficiently Tuning α-Reachable Graphs for Nearest Neighbor Search. CoRR Tian Zhang, Ashwin Padaki, Jiaming Liang, Zack Ives, Erik Waingarten
2026	A*	`conf`	Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness. SODA Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
2026	A*	`conf`	Streaming and Massively Parallel Algorithms for Euclidean Max-Cut. SODA Nicolas Menand, Erik Waingarten
2025	A*	`conf`	A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams. FOCS Sanjeev Khanna, Ashwin Padaki, Krish Singal, Erik Waingarten
2025	J	`jnl`	A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams. CoRR Sanjeev Khanna, Ashwin Padaki, Krish Singal, Erik Waingarten
2025	A*	`conf`	Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair. FOCS Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten
2025	J	`jnl`	Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair. CoRR Lorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten
2025	A*	`conf`	Average Distortion Sketching. FOCS Yiqiao Bao, Anubhav Baweja, Nicolas Menand, Erik Waingarten, Nathan White, Tian Zhang
2025	A*	`conf`	Instance-Optimal Uniformity Testing and Tracking. FOCS Guy Blanc, Clément L. Canonne, Erik Waingarten
2025	J	`jnl`	Instance-Optimal Uniformity Testing and Tracking. CoRR Guy Blanc, Clément L. Canonne, Erik Waingarten
2025	A*	`conf`	Lower Bounds for Convexity Testing. SODA Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten
2025	A*	`conf`	Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning. STOC Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, Erik Waingarten
2025	J	`jnl`	Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning. CoRR Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, Erik Waingarten
2025	A*	`conf`	Nearly Tight Bounds on Testing of Metric Properties. SODA Yiqiao Bao, Sampath Kannan, Erik Waingarten
2025	A*	`conf`	Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures. ICML Jie Gao, Rajesh Jayaram, Benedikt Kolbe, Shay Sapir, Chris Schwiegelshohn, Sandeep Silwal, Erik Waingarten
2025	J	`jnl`	Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures. CoRR Jie Gao, Rajesh Jayaram, Benedikt Kolbe, Shay Sapir, Chris Schwiegelshohn, Sandeep Silwal, Erik Waingarten
2025	J	`jnl`	Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness. CoRR Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
2025	J	`jnl`	Streaming and Massively Parallel Algorithms for Euclidean Max-Cut. CoRR Nicolas Menand, Erik Waingarten
2025	A*	`conf`	The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction. SODA Moses Charikar, Erik Waingarten
2024	A*	`conf`	A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. SODA Moses Charikar, Michael Kapralov, Erik Waingarten
2024	J	`jnl`	A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations. CoRR Moses Charikar, Michael Kapralov, Erik Waingarten
2024	J	`jnl`	Average-Distortion Sketching. CoRR Yiqiao Bao, Anubhav Baweja, Nicolas Menand, Erik Waingarten, Nathan White, Tian Zhang
2024	A*	`conf`	Data-Dependent LSH for the Earth Mover's Distance. STOC Rajesh Jayaram, Erik Waingarten, Tian Zhang
2024	J	`jnl`	Data-Dependent LSH for the Earth Mover's Distance. CoRR Rajesh Jayaram, Erik Waingarten, Tian Zhang
2024	J	`jnl`	Lower Bounds for Convexity Testing. CoRR Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten
2024	J	`jnl`	Nearly Tight Bounds on Testing of Metric Properties. CoRR Yiqiao Bao, Sampath Kannan, Erik Waingarten
2023	J	`jnl`	A Near-Linear Time Algorithm for the Chamfer Distance. CoRR Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, Erik Waingarten
2023	A*	`conf`	Fast Algorithms for a New Relaxation of Optimal Transport. COLT Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten
2023	J	`jnl`	Fast Algorithms for a New Relaxation of Optimal Transport. CoRR Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten
2023	A*	`conf`	Near-Linear Time Algorithm for the Chamfer Distance. NeurIPS Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, Erik Waingarten
2023	A*	`conf`	Simple, Scalable and Effective Clustering via One-Dimensional Projections. NeurIPS Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, Erik Waingarten
2023	J	`jnl`	Simple, Scalable and Effective Clustering via One-Dimensional Projections. CoRR Moses Charikar, Monika Henzinger, Lunjia Hu, Maximilian Vötsch, Erik Waingarten
2023	A*	`conf`	Streaming Euclidean MST to a Constant Factor. STOC Xi Chen, Vincent Cohen-Addad, Rajesh Jayaram, Amit Levi, Erik Waingarten
2022	J	`jnl`	Approximating the distance to monotonicity of Boolean functions. Random Struct. Algorithms Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
2022	A*	`conf`	Estimation of Entropy in Constant Space with Improved Sample Complexity. NeurIPS Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
2022	J	`jnl`	Estimation of Entropy in Constant Space with Improved Sample Complexity. CoRR Maryam Aliakbarpour, Andrew McGregor, Jelani Nelson, Erik Waingarten
2022	A*	`conf`	Finding Monotone Patterns in Sublinear Time, Adaptively. ICALP Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten
2022	A*	`conf`	New streaming algorithms for high dimensional EMD and MST. STOC Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2022	A*	`conf`	Polylogarithmic Sketches for Clustering. ICALP Moses Charikar, Erik Waingarten
2022	J	`jnl`	Polylogarithmic Sketches for Clustering. CoRR Moses Charikar, Erik Waingarten
2022	J	`jnl`	Streaming Euclidean MST to a Constant Factor. CoRR Vincent Cohen-Addad, Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2022	J	`jnl`	The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction. CoRR Moses Charikar, Erik Waingarten
2021	A*	`conf`	Approximate Nearest Neighbors Beyond Space Partitions. SODA Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2021	A*	`conf`	Learning and testing junta distributions with sub cube conditioning. COLT Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2021	J	`jnl`	New Streaming Algorithms for High Dimensional EMD and MST. CoRR Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2021	A*	`conf`	Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning. SODA Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
2020	A*	`conf`	Approximating the Distance to Monotonicity of Boolean Functions. SODA Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
2020	J	`jnl`	Learning and Testing Junta Distributions with Subcube Conditioning. CoRR Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten
2020	A*	`conf`	Nearly optimal edge estimation with independent set queries. SODA Xi Chen, Amit Levi, Erik Waingarten
2019	J	`jnl`	Approximating the Distance to Monotonicity of Boolean Functions. CoRR Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
2019	J	`jnl`	Approximating the Distance to Monotonicity of Boolean Functions. Electron. Colloquium Comput. Complex. Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten
2019	A*	`conf`	Finding Monotone Patterns in Sublinear Time. FOCS Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten
2019	J	`jnl`	Finding monotone patterns in sublinear time. CoRR Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten
2019	J	`jnl`	Finding monotone patterns in sublinear time. Electron. Colloquium Comput. Complex. Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten
2019	A	`conf`	Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. ITCS Amit Levi, Erik Waingarten
2019	J	`jnl`	Nearly optimal edge estimation with independent set queries. CoRR Xi Chen, Amit Levi, Erik Waingarten
2019	A*	`conf`	On Mean Estimation for General Norms with Statistical Queries. COLT Jerry Li, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2019	J	`jnl`	On Mean Estimation for General Norms with Statistical Queries. CoRR Jerry Li, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2019	J	`jnl`	Optimal Adaptive Detection of Monotone Patterns. CoRR Omri Ben-Eliezer, Shoham Letzter, Erik Waingarten
2019	J	`jnl`	Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. CoRR Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
2019	J	`jnl`	Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. Electron. Colloquium Comput. Complex. Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
2019	J	`jnl`	Testing Unateness Nearly Optimally. CoRR Xi Chen, Erik Waingarten
2019	A*	`conf`	Testing unateness nearly optimally. STOC Xi Chen, Erik Waingarten
2018	A*	`conf`	Data-dependent hashing via nonlinear spectral gaps. STOC Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2018	A*	`conf`	Hölder Homeomorphisms and Approximate Nearest Neighbors. FOCS Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2018	J	`jnl`	Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. CoRR Amit Levi, Erik Waingarten
2018	J	`jnl`	Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. Electron. Colloquium Comput. Complex. Amit Levi, Erik Waingarten
2018	J	`jnl`	Settling the Query Complexity of Non-adaptive Junta Testing. J. ACM Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2018	J	`jnl`	The fewest clues problem. Theor. Comput. Sci. Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson
2017	—	`conf`	Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. APPROX-RANDOM Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
2017	J	`jnl`	Adaptivity is exponentially powerful for testing monotonicity of halfspaces. CoRR Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
2017	A*	`conf`	Approximate near neighbors for general symmetric norms. STOC Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2017	J	`jnl`	Arboral satisfaction: Recognition and LP approximation. Inf. Process. Lett. Erik D. Demaine, Varun Ganesan, Vladislav Kontsevoi, Qipeng Liu, Quanquan C. Liu, Fermi Ma, Ofir Nachum, Aaron Sidford, Erik Waingarten, Daniel Ziegler
2017	J	`jnl`	Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness. CoRR Xi Chen, Erik Waingarten, Jinyu Xie
2017	A*	`conf`	Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness. STOC Xi Chen, Erik Waingarten, Jinyu Xie
2017	J	`jnl`	Boolean Unateness Testing with Õ(n CoRR Xi Chen, Erik Waingarten, Jinyu Xie
2017	A*	`conf`	Boolean Unateness Testing with Õ(n FOCS Xi Chen, Erik Waingarten, Jinyu Xie
2017	A*	`conf`	Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. SODA Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
2017	A	`conf`	Settling the Query Complexity of Non-Adaptive Junta Testing. CCC Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2017	J	`jnl`	Settling the query complexity of non-adaptive junta testing. CoRR Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2017	J	`jnl`	Settling the query complexity of non-adaptive junta testing. Electron. Colloquium Comput. Complex. Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2016	J	`jnl`	Approximate Near Neighbors for General Symmetric Norms. CoRR Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten
2016	J	`jnl`	Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors. CoRR Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
2016	J	`jnl`	Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. CoRR Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten
2016	Misc	`conf`	The Fewest Clues Problem. FUN Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson
2015	—	`conf`	Mario Kart Is Hard. JCDCGG Jeffrey Bosboom, Erik D. Demaine, Adam Hesterberg, Jayson Lynch, Erik Waingarten
2015	J	`jnl`	You Should Be Scared of German Ghost. J. Inf. Process. Erik D. Demaine, Fermi Ma, Matthew Susskind, Erik Waingarten
2014	Misc	`conf`	Playing Dominoes Is Hard, Except by Yourself. FUN Erik D. Demaine, Fermi Ma, Erik Waingarten