Exponentially improved algorithms and lower bounds for testing signed majorities

摘要

A signed majority function is a linear threshold function f:+11n+11 of the formf(x)=sign(ni=1ixi) 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(ni=1wixi?) for arbitrary real wi .We study the query complexity of testing whether an unknownf:+1?1n+1?1 is a signed majority function versus -far from every signed majority function.While it is known that the broader class of all linear threshold functions is testable with poly(1) queries (independent of n), prior to our work the best upper bound for signed majority functions wasO(n)poly(1) queries (via a non-adaptive algorithm), and the best lower bound was (logn) queries for non-adaptive algorithms.As our main results we exponentially improve both these prior bounds for testing signed majority functions:We give a poly(logn1) -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(1) queries. This directly implies a lower bound of (logn) 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(logn1) variables where a simple direct method can be applied. Analysis of the degree-1 Fourier coefficients plays an important role in our proofs.