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.