research-article

Testing juntas nearly optimally

Author:

Eric BlaisAuthors Info & Claims

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

Pages 151 - 158

https://doi.org/10.1145/1536414.1536437

Published: 31 May 2009 Publication History

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 and Elchanan Mossel. Approximation resistant predicates from pairwise independence. In Proc. 23rd Conf. on Computational Complexity, 2008.

Digital Library

[2]

Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free bits, PCPs and non-approximability -- towards tight results. SIAM J. Comput., 27(3):804--915, 1998.

Digital Library

[3]

Eric Blais. Improved bounds for testing juntas. In Proc. 12th Workshop RANDOM, pages 317--330, 2008.

Digital Library

[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, and Nick Littlestone. Learning in the presence of finitely or infinitely many irrelevant attributes. J. of Comp. Syst. Sci., 50(1):32--40, 1995.

Digital Library

[6]

Hana Chockler and Dan Gutfreund. A lower bound for testing juntas. Information Processing Letters, 90(6):301--305, 2004.

Digital Library

[7]

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, and Andrew Wan. Testing for concise representations. In Proc. 48th Symposium on Foundations of Computer Science, pages 549--558, 2007.

Digital Library

[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, and Alex Samorodnitsky. Testing juntas. J. Comput. Syst. Sci., 68(4):753--787, 2004.

Digital Library

[10]

Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. of the ACM, 45(4):653--750, 1998.

Digital Library

[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, and Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other two-variable CSPs? SIAM J. Comput., 37(1):319--357, 2007.

Digital Library

[15]

Elchanan Mossel. Gaussian bounds for noise correlation of functions and tight analysis of long codes. In Proc. 49th Symp. on Foundations of Computer Science, 2008.

Digital Library

[16]

Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. In Proc. 46th Symp. Foundations of Comp. Sci., pages 21--30, 2005.

Digital Library

[17]

Michal Parnas, Dana Ron, and Alex Samorodnitsky. Testing basic boolean formulae. SIAM J. Discret. Math., 16(1):20--46, 2003.

Digital Library

[18]

Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252--271, 1996.

Digital Library

[19]

J. Michael Steele. An Efron-Stein inequality for non--symmetric statistics. Ann. of Statistics, 14(2):753--758, 1986.

Cited By

Bao ZYao P(2025)On Testing and Learning Quantum Junta ChannelsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2025.352864847:4(2991-3002)Online publication date: Apr-2025
https://doi.org/10.1109/TPAMI.2025.3528648
Nadimpalli SPatel SMohar BShinkar IO'Donnell R(2024)Optimal Non-adaptive Tolerant Junta Testing via Local EstimatorsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649687(1039-1050)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649687
Nadimpalli SParham NVasconcelos FYuen HMohar BShinkar IO'Donnell R(2024)On the Pauli Spectrum of QAC0Proceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649662(1498-1506)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649662
Show More Cited By

Index Terms

Testing juntas nearly optimally
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

A function f:{ −1,1}ⁿ → { −1,1} is a k-junta if it depends on at most k of its variables. We consider the problem of tolerant testing of k-juntas, where the testing algorithm must accept any function that is ε-close to some k-junta and reject any ...
Settling the Query Complexity of Non-adaptive Junta Testing

We prove that any non-adaptive algorithm that tests whether an unknown Boolean function f:{0,1}ⁿ→ {0,1} is a k-junta or ϵ-far from every k-junta must make Ω^˜(k^3/2) / ϵ) many queries for a wide range of parameters k and ϵ. Our result dramatically ...
Testing juntas
Special issue on FOCS 2002

We show that a boolean valued function over n variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only J of them using a number of queries that depends only polynomially on J and the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

May 2009

750 pages

ISBN:9781605585062

DOI:10.1145/1536414

Program Chair:
Michael Mitzenmacher
Harvard University

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '09

Sponsor:

STOC '09: Symposium on Theory of Computing

May 31 - June 2, 2009

MD, Bethesda, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
514
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)2

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bao ZYao P(2025)On Testing and Learning Quantum Junta ChannelsIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2025.352864847:4(2991-3002)Online publication date: Apr-2025
https://doi.org/10.1109/TPAMI.2025.3528648
Nadimpalli SPatel SMohar BShinkar IO'Donnell R(2024)Optimal Non-adaptive Tolerant Junta Testing via Local EstimatorsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649687(1039-1050)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649687
Nadimpalli SParham NVasconcelos FYuen HMohar BShinkar IO'Donnell R(2024)On the Pauli Spectrum of QAC0Proceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649662(1498-1506)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649662
Chen XPatel S(2023)New Lower Bounds for Adaptive Tolerant Junta Testing2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00108(1778-1786)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00108
Blanc GKoch CStrassle CTan L(2023)A strong composition theorem for junta complexity and the boosting of property testers2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00107(1757-1777)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00107
Bshouty N(2023)An optimal tester for k-linearTheoretical Computer Science10.1016/j.tcs.2023.113759950:COnline publication date: 16-Mar-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113759
Bshouty N(2022)An Optimal Tester for k-LinearWALCOM: Algorithms and Computation10.1007/978-3-030-96731-4_17(201-212)Online publication date: 16-Mar-2022
https://doi.org/10.1007/978-3-030-96731-4_17
Iyer VTal AWhitmeyer M(2021)Junta distance approximation with sub-exponential queriesProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.24Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.24
De AMossel ENeeman JKhuller SVassilevska Williams V(2021)Robust testing of low dimensional functionsProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451115(584-597)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451115
Pallavoor RRaskhodnikova SWaingarten E(2021)Approximating the distance to monotonicity of Boolean functionsRandom Structures & Algorithms10.1002/rsa.2102960:2(233-260)Online publication date: 24-Jun-2021
https://doi.org/10.1002/rsa.21029
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten