Erik Waingarten

activity

20162026

most citedOptimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors

48 citations · 79 across the 36 of their papers we have counts for

collaborators

Showing cs.CCShow all

6 papers · 1 filter

cs.CC2024

Lower Bounds for Convexity Testing

Xi Chen, Anindya De, Shivam Nadimpalli +2

We consider the problem of testing whether an unknown and arbitrary set $S \subseteq R^{n}$ (given as a black-box membership oracle) is convex, versus $ε$ -far from…

cs.CC2018

Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

Amit Levi, Erik Waingarten

We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of $n$ -nodes graphs using rejection samp…

cs.CC2017

Boolean Unateness Testing with $O (n^{3/4})$ Adaptive Queries

Xi Chen, Erik Waingarten, Jinyu Xie

We give an adaptive algorithm which tests whether an unknown Boolean function $f : {0, 1}^{n} \to {0, 1}$ is unate, i.e. every variable of $f$ is either non-decreasing or non-…

cs.CC2017

Adaptivity is exponentially powerful for testing monotonicity of halfspaces

Xi Chen, Rocco A. Servedio, Li-Yang Tan +1

We give a $poly (lo g n, 1/ ε)$ -query adaptive algorithm for testing whether an unknown Boolean function $f : {- 1, 1}^{n} \to {- 1, 1}$ , which is promised to be a halfspace, i…

cs.CC2017★ 1 cited

Settling the query complexity of non-adaptive junta testing

Xi Chen, Rocco A. Servedio, Li-Yang Tan +2

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function $f : {0, 1}^{n} \to {0, 1}$ is a $k$ -junta or $ε$ -far from every $k$ -junta must make $\widet…