We study the complexity of approximating monotone Boolean functions with disjunctive normal form (DNF) formulas, exploring two main directions. First, we construct DNF approximators for arbitrary monotone functions achieving one-sided error: we show that every monotone $f$ can be $\eps$-approximated by a DNF $g$ of size $2^{n-\Omega_\eps(\sqrt{n})}$ satisfying $g(x) \le f(x) $ for all $x\in\{0,1\}^n$. This is the first non-trivial universal upper bound even for DNF approximators incurring two-sided error.
Next, we study the power of negations in DNF approximators for monotone functions. We exhibit monotone functions for which non-monotone DNFs perform better than monotone ones, giving separations with respect to both DNF size and width. Our results, when taken together with a classical theorem of Quine \cite{Qui54}, highlight an interesting contrast between approximation and exact computation in the DNF complexity of monotone functions, and they add to a line of work on the surprising role of negations in monotone complexity \cite{Raz85,Oko82,AG87}.
pdf of conference version
pdf of full version