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 2017Show all

4 papers · 1 filter

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…