Exponentially improved algorithms and lower bounds for testing signed majorities
D. Ron and R. Servedio.
In Algorithmica, 72(2), 2015, pp. 400--429.
Preliminary version in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013, pp. 1319--1336.

Abstract:

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:

• Upper bound: We give a $\poly(\log n, 1/\eps)$-query adaptive algorithm (which is computationally efficient) for this testing problem;
• Lower bound: 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 $\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.