Jinyu Xie

activity

20152018

most citedDistribution-free Junta Testing

9 citations · 21 across the 7 of their papers we have counts for

collaborators

Showing 2017Show all

3 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★ 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…

cs.CC2017★ 1 cited

Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness

Xi Chen, Erik Waingarten, Jinyu Xie

We prove a lower bound of $Ω ~ (n^{1/3})$ for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function $f:\{0,1\}^n\rightarrow…

Boolean Unateness Testing with O(n3/4) Adaptive Queries

Settling the query complexity of non-adaptive junta testing

Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness

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