We consider the problem of determining whether a given function
f : {0,1}^n -> {0,1} belongs to a certain class of Boolean functions
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 belongs to F or whether it differs from
every g in F on more than an epsilon-fraction of the domain elements.
The classes of functions we consider are singleton (``dictatorship'')
functions, monomials, and monotone DNF functions with a bounded number of
terms. In all cases we provide algorithms whose query complexity is
independent of n (the number of variables), and linear in 1/\epsilon./

We consider the problem of determining whether a given
function f : {0,1}^n -> {0,1} belongs to a certain class
of Boolean functions 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 belongs to F or whether it differs from every g in F
on more than an epsilon-fraction of the domain elements.

The classes of functions we consider are singleton (``dictatorship'')
functions, monomials, and monotone DNF 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 polynomial in the other relevant parameters.