A. Levy and E. Waingarten. Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. (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. DataDependent 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 Nonadaptive 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 Hashingbased Time–
Space Tradeoffs for Approximate Near Neighbors, proceedings of 28th ACMSIAM 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)

Erik Waingarten >