Testing juntas nearly optimally

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 (k^3/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.

REFERENCES

• 1: Per Austrin , Elchanan Mossel, Approximation Resistant Predicates from Pairwise Independence, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.249-258, June 22-26, 2008 [doi>10.1109/CCC.2008.20]
• 2: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 3: Eric Blais, Improved Bounds for Testing Juntas, Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, August 25-27, 2008, Boston, MA, USA [doi>10.1007/978-3-540-85363-3_26]
• 4: Eric Blais, Ryan O'Donnell, and Karl Wimmer. Polynomial regression under arbitrary product distributions. In Proc. 21st Conf. on Learning Theory, pages 193--204, 2008.
• 5: Avrim Blum , Lisa Hellerstein , Nick Littlestone, Learning in the presence of finitely or infinitely many irrelevant attributes, Journal of Computer and System Sciences, v.50 n.1, p.32-40, Feb. 1995 [doi>10.1006/jcss.1995.1004]
• 6: Hana Chockler , Dan Gutfreund, A lower bound for testing juntas, Information Processing Letters, v.90 n.6, p.301-305, 30 June 2004 [doi>10.1016/j.ipl.2004.01.023]
• 7: Ilias Diakonikolas , Homin K. Lee , Kevin Matulef , Krzysztof Onak , Ronitt Rubinfeld , Rocco A. Servedio , Andrew Wan, Testing for Concise Representations, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.549-558, October 21-23, 2007 [doi>10.1109/FOCS.2007.70]
• 8: Brad Efron and Charles Stein. The jackknife estimate of variance. Ann. of Stat., 9(3):586--596, 1981.
• 9: Eldar Fischer , Guy Kindler , Dana Ron , Shmuel Safra , Alex Samorodnitsky, Testing juntas, Journal of Computer and System Sciences, v.68 n.4, p.753-787, June 2004 [doi>10.1016/j.jcss.2003.11.004]
• 10: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 11: Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, 2001.
• 12: Timothy R. Hugues et al. Expression profiling using microarrays fabricated by an ink-jet oligonucleotide synthesizer. Nature Biotechnology, 19(4):342--347, 2001.
• 13: Samuel Karlin and Yosef Rinott. Applications of ANOVA type decompositions for comparisons of conditional variance statistics including jack-knife estimates. Ann. of Statistics, 10(2):485--501, 1982.
• 14: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O’Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM Journal on Computing, v.37 n.1, p.319-357, April 2007 [doi>10.1137/S0097539705447372]
• 15: Elchanan Mossel, Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.156-165, October 25-28, 2008 [doi>10.1109/FOCS.2008.44]
• 16: Elchanan Mossel , Ryan O'Donnell , Krzysztof Oleszkiewicz, Noise stability of functions with low in.uences invariance and optimality, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.21-30, October 23-25, 2005 [doi>10.1109/SFCS.2005.53]
• 17: Michal Parnas , Dana Ron , Alex Samorodnitsky, Testing Basic Boolean Formulae, SIAM Journal on Discrete Mathematics, v.16 n.1, p.20-46, 2003 [doi>10.1137/S0895480101407444]
• 18: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
• 19: J. Michael Steele. An Efron-Stein inequality for non--symmetric statistics. Ann. of Statistics, 14(2):753--758, 1986.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
Efron-Stein decomposition, juntas, property testing