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 or is 'far' from satisfying it? This is a fundamental question in property testing, where traditionally the testing algorithm is allowed to pick its queries among the entire set of inputs. Balcan, Blais, Blum and Yang have recently suggested restricting the tester to take its queries from a smaller random subset of polynomial size of the inputs. This model is called active testing, and in the extreme case when the size of the set we can query from is exactly the number of queries performed, it is known as passive testing. We prove that passive or active testing of k-linear functions (that is, sums of k variables among n over 2) requires Θ(k log n) queries, assuming k is not too large. This extends the case k = 1, (that is, dictator functions), analysed by Balcan, Blais, Blum and Yang. We also consider other classes of functions including low-degree polynomials, juntas, and partially symmetric functions. Our methods combine algebraic, combinatorial, and probabilistic techniques, including the Talagrand concentration inequality and the ErdÅ's-Rado theorem on Δ-systems.