Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions

We improve both upper and lower bounds for the distribution-free testing of monotone conjunctions. Given oracle access to an unknown Boolean function f:0,1n rightarrow 0,1 and sampling oracle access to an unknown distribution D over 0,1n, we present an tildeO(n1/3/ε5)-query algorithm that tests whether f is a monotone conjunction versus ε-far from any monotone conjunction with respect to D. This improves the previous best upper bound of tildeO(n1/2/ε) by Dolev and Ron when 1/ε is small compared to n. For some constant ε0>0, we also prove a lower bound of tildeOmega(n1/3) for the query complexity, improving the previous best lower bound of tildeOmega(n1/5) by Glasner and Servedio. Our upper and lower bounds are tight, up to a poly-logarithmic factor, when the distance parameter ε is a constant. Furthermore, the same upper and lower bounds can be extended to the distribution-free testing of general conjunctions, and the lower bound can be extended to that of decision lists and linear threshold functions.