Exponentially improved algorithms and lower bounds for testing signed majorities
Dana Ron, Rocco A. Servedio · Symposium on Discrete Algorithms · 2013
@) for arbitrary real wi, θ.We study the query complexity of testing whether an unknown f: {+1, −1}n → {+1, −1} is a signed majority function versus e-far from every signed majority function. While it is known [26] that the broader class of all linear threshold functions is testable with poly(1/e) queries (independent of n), prior to our work the best upper bound for signed majority functions was O(√n) · poly (1/e) queries (via a non-adaptive algorithm), and the best lower bound was Ω(log n) queries for non-adaptive algorithms [27].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/e)-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Ω(1) queries. This directly implies a lower bound of Ω(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/e) variables where a simple direct method can be applied. Analysis of the degree-1 Fourier coefficients plays an important role in our proofs.