Testing juntas nearly optimally
Eric Blais · 2009
A function on n variables is called a k-junta if it depends on at most k of its variables. In this article, we show that it is possible to test whether a function is a k-junta or is "far" from being a k-junta with O(kε + k log k ) queries, where epsilon is the approximation parameter. This result improves on the previous best upper bound of O (k3/2)ε queries and is asymptotically optimal, up to a logarithmic factor.