Exponentially improved algorithms and lower bounds for testing signed majorities

by Dana Ron and Rocco Servedio

Oded's comments

It is quite a rare feast to improve both the known upper and lower bounds on a natural problem by an exponential amount. Well, this is what this paper does... The problem is that of testing signed majority.

A point to stress at this occasion is that complexity of testing a property $\Pi$ does not necesassarily increase or decrease with respect to testing a subproperty or a superproperty of $\Pi$. Specifically, it was known that testing weighted majority (aka "linear threshold functions") can be done in complexity that is polynomially related to the proximity parameter. Likewise, it is very easy to test majority. The current property (i.e., signed majority) lies in between these two (generalized and restricted cases).

One begging open problem refers to the complexity of testing weighted majority when the weights are taken from an arbitrary fixed set (e.g., all integers of absolute value at most $B$). It seems that this can be handled for $B=1$ using the techniques of the current work (i.e., in this case the allowed weights are $-1,0,1$).

The original abstract

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:

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.

See TR13-096 of ECCC.

Back to list of Oded's choices.