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.