Adaptivity helps for testing juntas.
R. Servedio and L.-Y. Tan and J. Wright.
In 30th Conference on Computational Complexity (CCC), 2015, pp. 264--279.


Abstract:

We give a new lower bound on the query complexity of any non-adaptive algorithm for testing whether an unknown Boolean function is a k-junta versus epsilon-far from every k-junta. Our lower bound is that any non-adaptive algorithm must make Omega(( k log(k)) / ( epsilon^c log(log(k)/epsilon^c))) queries for this testing problem, where c is any absolute constant less than 1. For suitable values of epsilon this is asymptotically larger than the O(k log(k) + k/epsilon) query complexity of the best known adaptive algorithm [Blais,STOC'09] for testing juntas, and thus the new lower bound shows that adaptive algorithms are more powerful than non-adaptive algorithms for the junta testing problem.


Link to open-access LIPIcs conference version

Back to main papers page