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, 1}  n   → {0, 1} and sampling oracle access to an unknown distribution  D  over {0, 1}  n  , we present an  O ( n  1/3 /e 5 )-query algorithm that tests whether  f  is a monotone conjunction versus e-far from any monotone conjunction with respect to  D.  This improves the previous best upper bound of  O ( n  1/2 /e) by Dolev and Ron [DR11], when 1/e is small compared to  n.  For some constant e 0  > 0, we also prove a lower bound of Ω( n  1/3 ) for the query complexity, improving the previous best lower bound of Ω( n  1/5 ) by Glasner and Servedio [GS09]. Our upper and lower bounds are tight, up to a poly-logarithmic factor, when the distance parameter e 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.
['Xi Chen', 'Jinyu Xie']
Tight bounds for the distribution-free testing of monotone conjunctions