ECCC-Report TR13-096https://eccc.weizmann.ac.il/report/2013/096Comments and Revisions published for TR13-096en-usTue, 25 Jun 2013 13:41:31 +0300
Paper TR13-096
| Exponentially improved algorithms and lower bounds for testing signed majorities |
Dana Ron,
Rocco Servedio
https://eccc.weizmann.ac.il/report/2013/096A 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.
Tue, 25 Jun 2013 13:41:31 +0300https://eccc.weizmann.ac.il/report/2013/096