A \emph{signed majority function} is a linear threshold function $f: \plusminn \to \plusmin$ of the form $f(x)=\sign(\sum_{i=1}^n \sigma_i x_i)$ where each $\sigma_i \in \plusmin.$ Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form $\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: \plusminn \to \plusmin$ is a signed majority function versus $\eps$-far from every signed majority function. While it is known \cite{MORS:10} that the broader class of all linear threshold functions is testable with $\poly(1/\eps)$ queries (independent of $n$), prior to our work the best upper bound for signed majority functions was $O(\sqrt{n}) \cdot \poly(1/\eps)$ queries (via a non-adaptive algorithm), and the best lower bound was $\Omega(\log n)$ queries for non-adaptive algorithms~\cite{MORS:09random}.
As our main results we exponentially improve both these prior bounds for testing signed majority functions:
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 $\poly(\log n, 1/\eps)$ variables where a simple direct method can be applied. Analysis of the degree-1 Fourier coefficients plays an important role in our proofs.