Testing +1/-1 Weight Halfspaces.
K. Matulef and R. O'Donnell and R. Rubinfeld and R. Servedio.
13th International Workshop on Randomness and Computation (RANDOM), 2009, pp. 646--657.

Abstract:

We consider the problem of testing whether a Boolean function f: \{-1,1}^n \to \{-1,1\} is a unate reorientation of majority (UROM), i.e., a function of the form f(x) = sign(w_1 x_1 + w_2 x_2 + \cdots + w_n x_n) where the weights $w_i$ take values in \{-1,1\}. We show that the complexity of this problem is markedly different from the problem of testing whether f is a general halfspace with arbitrary weights. While the latter can be done with a number of queries that is independent of n (by results of \cite{MORS:09}), to distinguish whether f is a UROM versus \epsilon-far from all UROMs we prove that nonadaptive algorithms must make \Omega(\log n) queries. We complement this lower bound with a sublinear upper bound showing that O(\sqrt{n}\cdot poly(\frac{1}{\eps})) queries suffice.