Exponentially improved algorithms and lower bounds for testing signed majorities

摘要

A signed majority function is a linear threshold function f : {+1, -1}~n → {+1, -1} of the form f(x) = sign(∑_(i=1)~n σ_i x_i) where each σ_i ∈ {+1, -1}. Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form sign(Σ~(i=l)~n w_ix_i ~ θ) arbitrary real w_i,θ. We study the query complexity of testing whether an unknown f : {+1, - l}~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(l/∈) queries (independent of n), prior to our work the best upper bound for signed majority functions was O(√n) ?poly(1/∈) 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/∈)-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'.