On active and passive testing

Given a property of Boolean functions, what is the minimum number of queries required to determine with high probability if an input function satisfies this property? This is a fundamen-tal question in Property Testing, where traditionally the testing algorithm is allowed to pick its queries among the entire set of inputs. Balcan et al. have recently suggested to restrict the tester to take its queries from a smaller, typically random, subset of the inputs. This model is called active testing, in resemblance of active learning. Active testing gets more difficult as the size of the set we can query from decreases, and the extreme case is when it is exactly the number of queries we perform (so the algorithm actually has no choice). This is known as passive testing, or testing from random examples. In their paper, Balcan et al. have shown that active and passive testing of dictator functions is as hard as learning them, and requires Θ(logn) queries (unlike the classic model, in which it can be done in a constant number of queries). We extend this result to k-linear functions, proving that passive and active testing of them requires Θ(k logn) queries, assuming k is not too large