# Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions

arXiv: https://arxiv.org/abs/1511.03333 · HTML: https://mlsanity.com/paper/1511.03333/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2015.

## Built on by (most cited first, 1 of 1)

- [Superpolynomial Lower Bounds for Decision Tree Learning and Testing](https://mlsanity.com/paper/2210.06375/) (2022)

## Abstract (arXiv)

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.