Name
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ε + 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. We obtain the improved upper bound by introducing a new algorithm with one-sided error for testing juntas. Notably, the algorithm is a valid junta tester under very general conditions: it holds for functions with arbitrary finite domains and ranges, and it holds under any product distribution over the domain. A key component of the analysis of the new 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 of the variables. The structural lemma is proved using the Efron-Stein decomposition method. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1536414.1536437 | STOC |
Keywords | Field | DocType |
general condition,efron-stein decomposition method,arbitrary finite domain,approximation parameter,asymptotically optimal,structural lemma,new algorithm,k part,new structural result,k log k,property testing,algorithms,upper bound,decomposition method | Discrete mathematics,Combinatorics,Property testing,Upper and lower bounds,Decomposition method (constraint satisfaction),Logarithm,Partition (number theory),Asymptotically optimal algorithm,Lemma (mathematics),Mathematics | Conference |
ISSN | Citations | PageRank |
0737-8017 | 30 | 1.00 |
References | Authors | |
14 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eric Blais | 1 | 286 | 22.49 |