Erik Waingarten‎ > ‎

Publications

A. Levy 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.

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)

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. 

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. Invited to a special issue of ACM Transactions on Algorithms. (ARXIV)

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)
Comments