Erik Waingarten

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Streaming Euclidean MST to a constant factor	2024-05-08	Paper
scientific article; zbMATH DE number 7788359 (Why is no real title available?) (available as arXiv preprint)	2024-01-15	Paper
scientific article; zbMATH DE number 7788410 (Why is no real title available?)	2024-01-15	Paper
New streaming algorithms for high dimensional EMD and MST Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing	2023-12-08	Paper
Approximating the distance to monotonicity of Boolean functions Random Structures & Algorithms	2023-10-12	Paper
scientific article; zbMATH DE number 7559095 (Why is no real title available?) (available as arXiv preprint)	2022-07-18	Paper
Adaptivity is exponentially powerful for testing monotonicity of halfspaces (available as arXiv preprint)	2021-07-28	Paper
Nearly optimal edge estimation with independent set queries Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms	2021-02-02	Paper
Approximating the distance to monotonicity of Boolean functions Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms	2021-02-02	Paper
Settling the query complexity of non-adaptive junta testing (available as arXiv preprint)	2020-05-26	Paper
Learning and Testing Junta Distributions with Subcube Conditioning	2020-04-26	Paper
Testing unateness nearly optimally Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing	2020-01-30	Paper
Data-dependent hashing via nonlinear spectral gaps Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing	2019-08-22	Paper
Settling the query complexity of non-adaptive junta testing Journal of the ACM	2019-02-25	Paper
The fewest clues problem Theoretical Computer Science	2018-11-23	Paper
Optimal hashing-based time-space trade-offs for approximate near neighbors Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms	2018-07-16	Paper
Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing	2017-08-17	Paper
Arboral satisfaction: recognition and LP approximation Information Processing Letters	2017-08-16	Paper
The fewest clues problem	2017-07-17	Paper
Mario Kart is hard Lecture Notes in Computer Science	2017-02-01	Paper

Research outcomes over time

This page was built for person: Erik Waingarten