A signed majority function is a linear threshold function f : \{+1,1\}^n \to \{+1,1\} of the form
f(x)={\rm sign}(\sum_{i=1}^n \sigma_i x_i) where each \sigma_i \in \{+1,-1\}. Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form {\rm sign}(\sum_{i=1}^n w_i x_i - \theta) for arbitrary real w_i,\theta.

We study the query complexity of testing whether an unknown
f: \{+1,-1\}^n \to \{+1,-1\} is a signed majority function versus \epsilon-far from every signed majority function.
While it is known that the broader class of all linear threshold functions is testable with {\rm poly}(1/\epsilon) queries (independent of n), prior to our work the best upper bound for signed majority functions was
O(\sqrt{n}) \cdot {\rm poly}(1/\epsilon) queries (via a non-adaptive algorithm), and the best lower bound was \Omega(\log n) queries for non-adaptive algorithms.

As our main results we exponentially improve both these prior bounds for testing signed majority functions:

We give a {\rm poly}(\log n, 1/\epsilon)-query adaptive algorithm (which is computationally efficient) for this testing problem;

We show that any non-adaptive algorithm for testing the class of signed majorities to constant accuracy must make n^{\Omega(1)} queries. This directly implies a lower bound of \Omega(\log n) queries for any adaptive algorithm.

Our testing algorithm performs a sequence of restrictions together with consistency checks to ensure that each successive restriction is ``compatible'' with the function prior to restriction. This approach is used to transform the original n-variable testing problem into a testing problem over {\rm poly}(\log n, 1/\epsilon) variables where a simple direct method can be applied. Analysis of the degree-1 Fourier coefficients plays an important role in our proofs.