Testing Juntas Nearly Optimally

by Eric Blais

Oded's comments

Given the importance of dealing with functions that depend on few of their inputs (aka juntas), the problem of optimizing the complexity of testing juntas does deserve the attention it has received. The algorithm presented in this work is very appealing, and has query complexity $\tildeO(k/\epsilon)$, where $\epsilon$ is the proximity parameter.

The original abstract

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 log k)/epsilon queries, where epsilon is the approximation parameter. This result improves on the previous best upper bound of O(k^1.5 )/epsilon queries and is asymptotically optimal, up to a logarithmic factor. We obtain the improved upper bound by introducing a new algorithm with one-sided error for testing juntas. Notably, the new algorithm is a valid junta tester under very general conditions: it holds for functions with arbitrary .nite domains and ranges, and it holds under any product distribution over the domain. A key component of the analysis of the algorithm is a new structural result on juntas: roughly, we show that if a function f is .far. from being a k-junta, then f is .far. from being determined by k parts in a random partition. The structural lemma is proved using the Efron-Stein decomposition method.

Back to list of Oded's choices.