Xi Chen

activity

20092023

most citedNew algorithms and lower bounds for monotonicity testing

22 citations · 115 across the 31 of their papers we have counts for

collaborators

Showing 2014Show all

2 papers · 1 filter

cs.CC2014★ 2 cited

Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries

Xi Chen, Anindya De, Rocco A. Servedio +1

We prove a lower bound of $Ω (n^{1/2 - c})$ , for all $c > 0$ , on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an $n$ -variable Boolean function…

cs.CC2014★ 22 cited

New algorithms and lower bounds for monotonicity testing

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

We consider the problem of testing whether an unknown Boolean function $f$ is monotone versus $ε$ -far from every monotone function. The two main results of this paper are a new low…

Boolean function monotonicity testing requires (almost) n1/2 non-adaptive queries

New algorithms and lower bounds for monotonicity testing

Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries