Testing Basic Boolean Formulae
Michal Parnas, Dana Ron, Alex Samorodnitsky · SIAM Journal on Discrete Mathematics · 2002
We consider the problem of determining whether a given function $f:{\{0,1\}}^n\to{\{0,1\}}$ belongs to a certain class of Boolean functions $\cal F$ or whether it is far from the class. More precisely, given query access to the function f and given a distance parameter $\epsilon$, we would like to decide whether $f \in \cal F$ or whether it differs from every $g\in \cal F$ on more than an $\epsilon$-fraction of the domain elements. The classes of functions we consider are singleton ("dictatorship") functions, monomials, and monotone disjunctive normal form functions with a bounded number of terms. In all cases we provide algorithms whose query complexity is independent of n (the number of function variables), and linear in $1/\epsilon$.