Follow
Erik Waingarten
Erik Waingarten
University of Pennsylvania
Verified email at cs.columbia.edu - Homepage
Title
Cited by
Cited by
Year
Optimal hashing-based time-space trade-offs for approximate near neighbors
A Andoni, T Laarhoven, I Razenshteyn, E Waingarten
Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete …, 2017
1642017
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
X Chen, E Waingarten, J Xie
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017
682017
Approximate near neighbors for general symmetric norms
A Andoni, HL Nguyen, A Nikolov, I Razenshteyn, E Waingarten
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017
442017
Data-dependent hashing via nonlinear spectral gaps
A Andoni, A Naor, A Nikolov, I Razenshteyn, E Waingarten
Proceedings of the 50th annual ACM SIGACT symposium on theory of computing …, 2018
382018
Settling the query complexity of non-adaptive junta testing
X Chen, RA Servedio, LY Tan, E Waingarten, J Xie
Journal of the ACM (JACM) 65 (6), 1-18, 2018
372018
Hölder homeomorphisms and approximate nearest neighbors
A Andoni, A Naor, A Nikolov, I Razenshteyn, E Waingarten
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS …, 2018
372018
Approximating the distance to monotonicity of boolean functions
RKS Pallavoor, S Raskhodnikova, E Waingarten
Random Structures & Algorithms 60 (2), 233-260, 2022
352022
Random restrictions of high dimensional distributions and uniformity testing with subcube conditioning
CL Canonne, X Chen, G Kamath, A Levi, E Waingarten
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA …, 2021
342021
Learning and testing junta distributions with sub cube conditioning
X Chen, R Jayaram, A Levi, E Waingarten
Conference on Learning Theory, 1060-1113, 2021
292021
New streaming algorithms for high dimensional EMD and MST
X Chen, R Jayaram, A Levi, E Waingarten
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing …, 2022
232022
Boolean unateness testing with õ (n^{3/4}) adaptive queries
X Chen, E Waingarten, J Xie
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017
222017
Nearly optimal edge estimation with independent set queries
X Chen, A Levi, E Waingarten
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020
192020
Finding monotone patterns in sublinear time
O Ben-Eliezer, C Canonne, S Letzter, E Waingarten
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS …, 2019
162019
Lower bounds for tolerant junta and unateness testing via rejection sampling of graphs
A Levi, E Waingarten
arXiv preprint arXiv:1805.01074, 2018
152018
Mario kart is hard
J Bosboom, ED Demaine, A Hesterberg, J Lynch, E Waingarten
Japanese Conference on Discrete and Computational Geometry and Graphs, 49-59, 2015
152015
The fewest clues problem
ED Demaine, F Ma, A Schvartzman, E Waingarten, S Aaronson
Theoretical Computer Science 748, 28-39, 2018
142018
On mean estimation for general norms with statistical queries
J Li, A Nikolov, I Razenshteyn, E Waingarten
Conference on Learning Theory, 2158-2172, 2019
132019
Streaming euclidean mst to a constant factor
X Chen, V Cohen-Addad, R Jayaram, A Levi, E Waingarten
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 156-169, 2023
102023
Testing unateness nearly optimally
X Chen, E Waingarten
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing …, 2019
102019
Estimation of entropy in constant space with improved sample complexity
M Aliakbarpour, A McGregor, J Nelson, E Waingarten
Advances in Neural Information Processing Systems 35, 32474-32486, 2022
92022
The system can't perform the operation now. Try again later.
Articles 1–20