research-article

Public Access

Settling the Query Complexity of Non-adaptive Junta Testing

Authors:

Rocco A. Servedio,

Erik Waingarten,

Jinyu XieAuthors Info & Claims

Journal of the ACM (JACM), Volume 65, Issue 6

Article No.: 40, Pages 1 - 18

https://doi.org/10.1145/3213772

Published: 26 November 2018 Publication History

All formats PDF

Abstract

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 improves previous lower bounds and is essentially optimal since there is a known non-adaptive junta tester which makes Ω^˜(k^3/2) / ϵ queries. Combined with the known existence of an adaptive tester which makes O(klog k + k /ϵ) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.

References

[1]

José A. Adell and Pedro Jodrá. 2006. Exact Kolmogorov and total variation distances between some familiar discrete distributions. J. Inequal. Appl. 2006, 1 (2006), 1--8.

[2]

N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron. 2005. Testing Reed-Muller codes. IEEE Trans. Inform. Theor. 51, 11 (2005), 4032--4039.

Digital Library

[3]

Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor, and Sofya Raskhodnikova. 2016. Testing unateness of real-valued functions. CoRR abs/1608.07652 (2016).

[4]

A. Belovs and E. Blais. 2016. A polynomial lower bound for testing monotonicity. In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC'16). ACM, 1021--1032.

Digital Library

[5]

Arthur J. Bernstein. 1967. Maximally connected arrays on the n-cube. SIAM J. Appl. Math. 15, 6 (1967), 1485--1489.

[6]

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. 2010. Optimal testing of Reed-Muller codes. In 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS’10). IEEE Computer Society, 488--497.

Digital Library

[7]

Eric Blais. 2008. Improved bounds for testing juntas. In Proceedings of the 12th International Workshop on Randomization (RANDOM'08). Springer, 317--330.

Digital Library

[8]

Eric Blais. 2009. Testing juntas nearly optimally. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC’09). ACM, 151--158.

Digital Library

[9]

Eric Blais, Joshua Brody, and Kevin Matulef. 2011. Property testing lower bounds via communication complexity. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC'11). IEEE Computer Society, 210--220.

Digital Library

[10]

Eric Blais and Daniel M. Kane. 2012. Tight bounds for testing k-linearity. In Proceedings of the 16th International Workshop on Randomization (RANDOM'12). Springer, 435--446.

[11]

M. Blum, M. Luby, and R. Rubinfeld. 1993. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci. 47, 3 (1993), 549--595.

Digital Library

[12]

Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf. 2013. The non-adaptive query complexity of testing k-parities. Chicago J. Theor. Comput. Sci. Article 06 (2013), 1--11.

[13]

Deeparnab Chakrabarty and C. Seshadhri. 2013. A o(n) monotonicity tester for boolean functions over the hypercube. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC'13). ACM, 411--418.

Digital Library

[14]

Deeparnab Chakrabarty and C. Seshadhri. 2016. A Õ(n) non-adaptive tester for unateness. CoRR abs/1608.06980 (2016).

[15]

Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan. 2015. Boolean function monotonicity testing requires (almost) n<sup>1/2</sup> non-adaptive queries. In Proceedings of the 47th ACM Symposium on Theory of Computing (STOC'15). ACM, 519--528.

Digital Library

[16]

X. Chen, R. Servedio, and L.-Y. Tan. 2014. New algorithms and lower bounds for testing monotonicity. In Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS'14). IEEE Computer Society, 286--295.

Digital Library

[17]

H. Chockler and D. Gutfreund. 2004. A lower bound for testing juntas. Inform. Process. Lett. 90, 6 (2004), 301--305.

Digital Library

[18]

I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld, R. Servedio, and A. Wan. 2007. Testing for concise representations. In Proceedings of the 48th Annual Symposium on Computer Science (FOCS’07). IEEE Computer Society, 549--558.

Digital Library

[19]

D. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge.

Digital Library

[20]

E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky. 2004. Testing juntas. J. Comput. Syst. Sci. 68, 4 (2004), 753--787.

Digital Library

[21]

E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky. 2002. Monotonicity testing over general poset domains. In Proceedings of the 34th Annual ACM Symposium on the Theory of Computing. ACM, 474--483.

Digital Library

[22]

Peter Frankl. 1983. On the trace of finite sets. J. Comb. Theor. Ser. A 34, 1 (1983), 41--45.

[23]

O. Goldreich (Ed.). 2010. Property Testing: Current Research and Surveys. LNCS 6390. Springer.

Digital Library

[24]

Oded Goldreich. 2017. Introduction to Property Testing. Cambridge University Press.

[25]

O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samordinsky. 2000. Testing monotonicity. Combinatorica 20, 3 (2000), 301--337.

[26]

P. Gopalan, R. O’Donnell, R. Servedio, A. Shpilka, and K. Wimmer. 2011. Testing fourier dimensionality and sparsity. SIAM J. on Computing 40, 4 (2011), 1075--1100.

Digital Library

[27]

Larry H. Harper. 1964. Optimal assignments of numbers to vertices. SIAM J. Appl. Math. 12, 1 (1964), 131--135.

[28]

Sergiu Hart. 1976. A note on the edges of the n-cube. Disc. Math. 14, 2 (1976), 157--163.

Digital Library

[29]

Subhash Khot, Dor Minzer, and Muli Safra. 2015. On monotonicity testing and Boolean isoperimetric type theorems. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS'15). IEEE Computer Society, 52--58.

Digital Library

[30]

Subhash Khot and Igor Shinkar. 2016. An O(n) queries adaptive tester for unateness. In Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 37:1--37:7.

[31]

J. H. Lindsey. 1964. Assignment of numbers to vertices. Amer. Math. Monthly 71, 5 (1964), 508--516.

[32]

K. Matulef, R. O’Donnell, R. Rubinfeld, and R. Servedio. 2010. Testing halfspaces. SIAM J. on Comput. 39, 5 (2010), 2004--2047.

Digital Library

[33]

Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A. Servedio. 2009. Testing ± 1-weight halfspace. In Proceedings of the 13th International Workshop on Randomization (RANDOM'09). Springer, 646--657.

Digital Library

[34]

M. Parnas, D. Ron, and A. Samorodnitsky. 2002. Testing basic boolean formulae. SIAM J. Disc. Math. 16, 1 (2002), 20--46.

Digital Library

[35]

D. Ron. 2008. Property testing: A learning theory perspective. Foundations and Trends in Machine Learning 1, 3 (2008), 307--402.

Digital Library

[36]

D. Ron. 2010. Algorithmic and analysis techniques in property testing. Found. Trends Theor. Comput. Sci. 5, 2 (2010), 73--205.

Digital Library

[37]

D. Ron and R. Servedio. 2013. Exponentially improved algorithms and lower bounds for testing signed majorities. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13). SIAM, 1319--1336.

Digital Library

[38]

Dana Ron and Gilad Tsur. 2011. Testing Computability by Width-Two OBDDs. Technical Report 11(041). Electronic Colloquium on Computational Complexity (ECCC). available at http://eccc.hpi-web.de/report/2011/041/.

[39]

B. Roos. 2000. Binomial approximation to the Poisson binomial distribution: The Krawtchouk expansion. Theory Probab. Appl. 45, 2 (2000), 328--344.

[40]

Rocco Servedio, Li-Yang Tan, and John Wright. 2015. Adaptivity helps for testing juntas. In Proceedings of the 30th Conference on Computational Complexity (CCC'15). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 264--279.

Digital Library

Cited By

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
Gong SNong QFang JDu D(2024)Algorithms for Cardinality-Constrained Monotone DR-Submodular Maximization with Low Adaptivity and Query ComplexityJournal of Optimization Theory and Applications10.1007/s10957-023-02353-7200:1(194-214)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s10957-023-02353-7
(2023)An adaptive algorithm for maximization of non-submodular function with a matroid constraintJournal of Industrial and Management Optimization10.3934/jimo.202203119:3(2050-2070)Online publication date: 2023
https://doi.org/10.3934/jimo.2022031
Show More Cited By

Index Terms

Settling the Query Complexity of Non-adaptive Junta Testing
1. Theory of computation
  1. Design and analysis of algorithms
    1. Streaming, sublinear and near linear time algorithms
      1. Lower bounds and information complexity

Recommendations

Distribution-free Junta Testing

We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability ...
Testing juntas nearly optimally
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

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 ...
Settling the query complexity of non-adaptive junta testing
CCC '17: Proceedings of the 32nd Computational Complexity Conference

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 [EQUATION](k^3/2 /ε) many queries for a wide range of parameters k and ε. Our result ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 65, Issue 6

December 2018

331 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3293435

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2018 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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 November 2018

Accepted: 01 July 2018

Revised: 01 April 2018

Received: 01 September 2017

Published in JACM Volume 65, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF
NSF Graduate Research Fellowship

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
459
Total Downloads

Downloads (Last 12 months)108
Downloads (Last 6 weeks)18

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Gong SNong QFang JDu D(2024)Algorithms for Cardinality-Constrained Monotone DR-Submodular Maximization with Low Adaptivity and Query ComplexityJournal of Optimization Theory and Applications10.1007/s10957-023-02353-7200:1(194-214)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s10957-023-02353-7
(2023)An adaptive algorithm for maximization of non-submodular function with a matroid constraintJournal of Industrial and Management Optimization10.3934/jimo.202203119:3(2050-2070)Online publication date: 2023
https://doi.org/10.3934/jimo.2022031
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
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
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
Xie ZQiu D(2020)Quantum and classical query complexities for generalized Deutsch–Jozsa problemsQuantum Information Processing10.1007/s11128-020-02652-219:5Online publication date: 25-Mar-2020
https://dl.acm.org/doi/10.1007/s11128-020-02652-2

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents