More Web Proxy on the site http://driver.im/

research-article

Public Access

Distribution-free Junta Testing

Authors:

Rocco A. Servedio,

Jinyu XieAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 15, Issue 1

Article No.: 1, Pages 1 - 23

https://doi.org/10.1145/3264434

Published: 24 September 2018 Publication History

All formats PDF

Abstract

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 distribution over {0,1}ⁿ. Our first main result is that distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses Õ(k²)/ϵ queries (independent of n). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free k-junta testing algorithm must make Ω(2^k/3) queries even to test to accuracy ϵ = 1/3. These bounds establish that while the optimal query complexity of non-adaptive k-junta testing is 2^Θ(k), for adaptive testing it is poly(k), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

References

[1]

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

Digital Library

[2]

Noga Alon and Amit Weinstein. 2012. Local correction of juntas. Inf. Process. Lett. 112, 6 (2012), 223--226.

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.

[4]

Aleksandrs Belovs and Eric Blais. 2016. A polynomial lower bound for testing monotonicity. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC’16). ACM, New York, NY, 1021--1032.

Digital Library

[5]

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

Digital Library

[6]

Eric Blais. 2008. Improved bounds for testing juntas. In Proceedings of the International Conference on Randomization and Computation (RANDOM’08). 317--330.

Digital Library

[7]

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

Digital Library

[8]

Eric Blais, Joshua Brody, and Kevin Matulef. 2011. Property testing lower bounds via communication complexity. In Proceedings of the Computational Complexity Conference (CCC’11). 210--220.

Digital Library

[9]

Eric Blais and Daniel M. Kane. 2012. Tight bounds for testing k-linearity. In Proceedings of the International Conference on Randomization and Computation (RANDOM’12). 435--446.

[10]

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

Digital Library

[11]

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

[12]

Deeparnab Chakrabarty and C. Seshadhri. 2013. An o(n) monotonicity tester for Boolean functions over the hypercube. In Proceedings of the 45th ACM Symposium on Theory of Computing. 411--418.

Digital Library

[13]

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

[14]

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. 519--528.

Digital Library

[15]

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

Digital Library

[16]

Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. 2017a. Settling the query complexity of non-adaptive junta testing. In Proceedings of the 32nd Computational Complexity Conference (CCC’17). 26:1--26:19.

Digital Library

[17]

Xi Chen, Erik Waingarten, and Jinyu Xie. 2017b. Beyond talagrand functions: New lower bounds for testing monotonicity and unateness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC’17). 523--536.

Digital Library

[18]

Xi Chen, Erik Waingarten, and Jinyu Xie. 2017c. Boolean unateness testing with Õ(n<sup>3/4</sup>) adaptive queries. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17). 868--879.

[19]

Xi Chen and Jinyu Xie. 2016. Tight bounds for the distribution-free testing of monotone conjunctions. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16). 54--71.

Digital Library

[20]

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

Digital Library

[21]

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). 549--558.

Digital Library

[22]

E. Dolev and D. Ron. 2011. Distribution-free testing for monomials with a sublinear number of queries. Theory Comput. 7, 1 (2011), 155--176.

[23]

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

[24]

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

Digital Library

[25]

Dana Glasner and Rocco A. Servedio. 2009. Distribution-free testing lower bound for basic boolean functions. Theory Comput. 5, 1 (2009), 191--216.

[26]

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

Digital Library

[27]

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

[28]

O. Goldreich, S. Goldwasser, and D. Ron. 1998. Property testing and its connection to learning and approximation. J. ACM 45 (1998), 653--750.

Digital Library

[29]

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

Digital Library

[30]

S. Halevy and E. Kushilevitz. 2007. Distribution-free property testing. SIAM J. Comput. 37, 4 (2007), 1107--1138.

Digital Library

[31]

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. 52--58.

Digital Library

[32]

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.

[33]

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

Digital Library

[34]

Kevin Matulef, Ryan O’Donnell, Ronitt Rubinfeld, and Rocco A. Servedio. 2009. Testing ±1-weight halfspace. In Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the International Conference on Randomization and Computation (APPROX-RANDOM’09). 646--657.

[35]

M. Parnas, D. Ron, and A. Samorodnitsky. 2002. Testing basic boolean formulae. SIAM J. Disc. Math. 16 (2002), 20--46. Retrieved from citeseer.ifi.unizh.ch/parnas02testing.html.

Digital Library

[36]

D. Ron. 2008. Property testing: A learning theory perspective. Found. Trends Mach. Learn. 1, 3 (2008), 307--402.

Digital Library

[37]

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

Digital Library

[38]

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

Digital Library

[39]

Rocco Servedio, Li-Yang Tan, and John Wright. 2015. Adaptivity helps for testing juntas. In Proceedings of the 30th IEEE Conference on Computational Complexity, vol. 33 of LIPIcs, 264--279.

Digital Library

[40]

L. Valiant. 1984. A theory of the learnable. Commun. ACM 27, 11 (1984), 1134--1142.

Digital Library

Cited By

Zhan HLi YXiong YPal ULu YCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)Free Lunch: Frame-level Contrastive Learning with Text Perceiver for Robust Scene Text Recognition in Lightweight ModelsProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681045(6202-6211)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681045
Hu CKandappu TLiu YMascolo CMa D(2024)BreathPro: Monitoring Breathing Mode during Running with EarablesProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/36596078:2(1-25)Online publication date: 15-May-2024
https://dl.acm.org/doi/10.1145/3659607
Gao XPang YLiu YHan MYu JWang WChen Y(2024)Multimodal Visual-Semantic Representations Learning for Scene Text RecognitionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/364655120:7(1-18)Online publication date: 27-Mar-2024
https://dl.acm.org/doi/10.1145/3646551
Show More Cited By

Index Terms

Distribution-free Junta Testing
1. Theory of computation
  1. Design and analysis of algorithms
    1. Streaming, sublinear and near linear time 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 ...
Distribution-free junta testing
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 15, Issue 1

January 2019

366 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3281277

Editor:
Aravind Srinivasan
University of Maryland, USA

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 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 September 2018

Accepted: 01 July 2018

Received: 01 February 2018

Published in TALG Volume 15, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
524
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhan HLi YXiong YPal ULu YCai JKankanhalli MPrabhakaran BBoll SSubramanian RZheng LSingh VCesar PXie LXu D(2024)Free Lunch: Frame-level Contrastive Learning with Text Perceiver for Robust Scene Text Recognition in Lightweight ModelsProceedings of the 32nd ACM International Conference on Multimedia10.1145/3664647.3681045(6202-6211)Online publication date: 28-Oct-2024
https://dl.acm.org/doi/10.1145/3664647.3681045
Hu CKandappu TLiu YMascolo CMa D(2024)BreathPro: Monitoring Breathing Mode during Running with EarablesProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/36596078:2(1-25)Online publication date: 15-May-2024
https://dl.acm.org/doi/10.1145/3659607
Gao XPang YLiu YHan MYu JWang WChen Y(2024)Multimodal Visual-Semantic Representations Learning for Scene Text RecognitionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/364655120:7(1-18)Online publication date: 27-Mar-2024
https://dl.acm.org/doi/10.1145/3646551
Hong SHuu QViet DThi Thuy QQuoc T(2023)Learning binary codes for fast image retrieval with sparse discriminant analysis and deep autoencodersIntelligent Data Analysis10.3233/IDA-22668727:3(809-831)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.3233/IDA-226687
Li XWang TZhang WNiu XZhang TZhao TWang YWang Y(2023)An LSTM based cross-site scripting attack detection scheme for Cloud Computing environmentsJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00483-x12:1Online publication date: 8-Aug-2023
https://dl.acm.org/doi/10.1186/s13677-023-00483-x
Maratha PGupta K(2023)Linear optimization and fuzzy-based clustering for WSNs assisted internet of thingsMultimedia Tools and Applications10.1007/s11042-021-11850-882:4(5161-5185)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1007/s11042-021-11850-8
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
Liu JZha ZHong RWang MZhang YWen Chen CCucchiara RHua XQi GRicci EZhang ZZimmermann R(2020)Dual Context-Aware Refinement Network for Person SearchProceedings of the 28th ACM International Conference on Multimedia10.1145/3394171.3413878(3450-3459)Online publication date: 12-Oct-2020
https://dl.acm.org/doi/10.1145/3394171.3413878
Zheng KLiu WLiu JZha ZMei TWen Chen CCucchiara RHua XQi GRicci EZhang ZZimmermann R(2020)Hierarchical Gumbel Attention Network for Text-based Person SearchProceedings of the 28th ACM International Conference on Multimedia10.1145/3394171.3413864(3441-3449)Online publication date: 12-Oct-2020
https://dl.acm.org/doi/10.1145/3394171.3413864
Liu XYu YLi XZhao YGuo G(undefined)TCSD: Triple Complementary Streams Detector for Comprehensive Deepfake DetectionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/3558004
https://dl.acm.org/doi/10.1145/3558004

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