9 citations · 21 across the 7 of their papers we have counts for
4 papers · 1 filter
Distribution-free Junta Testing
Xi Chen, Zhengyang Liu, Rocco A. Servedio +2
We study the problem of testing whether an unknown -variable Boolean function is a -junta in the distribution-free property testing model, where the distance between function…
Boolean Unateness Testing with Adaptive Queries
Xi Chen, Erik Waingarten, Jinyu Xie
We give an adaptive algorithm which tests whether an unknown Boolean function is unate, i.e. every variable of is either non-decreasing or non-…
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 is a -junta or -far from every -junta must make $\widet…
Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness
Xi Chen, Erik Waingarten, Jinyu Xie
We prove a lower bound of for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function $f:\{0,1\}^n\rightarrow…