DNF Formulas are Efficiently Testable with Relative Error.
X. Chen and W. Pires and T. Pitassi and R. Servedio.
In 67th IEEE Symposium on Theory of Computing (FOCS), 2026.


Abstract:

We give a $\poly(s,1/\eps)$-query algorithm for testing whether an unknown and arbitrary function $f: \zo^n \to \zo$ is an $s$-term DNF, in the challenging \emph{relative-error} framework for Boolean function property testing that was recently introduced and studied in a number of works. This gives the first example of a rich and natural class of functions which may depend on a super-constant number of variables and yet is efficiently testable in the relative-error model with constant query complexity.

A crucial new ingredient enabling our approach is a novel decomposition of any $s$-term DNF formula into ``local clusters'' of terms. Our results demonstrate that this new decomposition can be usefully exploited for algorithms even when the $s$-term DNF is not explicitly given; we believe that this decomposition may have applications in other contexts.

Link to full version


Back to main papers page