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

research-article

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

Authors:

Clément L. Canonne,

Dana RonAuthors Info & Claims

ACM Transactions on Computation Theory (TOCT), Volume 11, Issue 4

Article No.: 24, Pages 1 - 33

https://doi.org/10.1145/3337789

Published: 22 July 2019 Publication History

Abstract

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 function that is ε′-far from every k′-junta for some ε′ = O(ε) and k′ = O(k).

Our first result is an algorithm that solves this problem with query complexity polynomial in k and 1/ε. This result is obtained via a new polynomial-time approximation algorithm for submodular function minimization (SFM) under large cardinality constraints, which holds even when only given an approximate oracle access to the function.

Our second result considers the case where k′ = k. We show how to obtain a smooth tradeoff between the amount of tolerance and the query complexity in this setting. Specifically, we design an algorithm that, given ρ ∈ (0,1), accepts any function that is ε ρ/16-close to some k-junta and rejects any function that is ε-far from every k-junta. The query complexity of the algorithm is O (k log k/ε ρ (1-ρ)^k.

Finally, we show how to apply the second result to the problem of tolerant isomorphism testing between two unknown Boolean functions f and g. We give an algorithm for this problem whose query complexity only depends on the (unknown) smallest k such that either f or g is close to being a k-junta.

References

[1]

Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu. 2007. Estimating the distance to a monotone function. Rand. Struct. Algor. 31, 3 (2007), 371--383.

Digital Library

[2]

Noga Alon and Eric Blais. 2010. Testing Boolean function isomorphism. In Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the International Conference on Randomization and Computation (APPROX--RANDOM’10), Maria J. Serna, Ronen Shaltiel, Klaus Jansen, and José D. P. Rolim (Eds.), Lecture Notes in Computer Science, Vol. 6302. Springer, Berlin, 394--405.

Digital Library

[3]

Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, and Arie Matsliah. 2013. Nearly tight bounds for testing function isomorphism. SIAM J. Comput. 42, 2 (2013), 459--493.

[4]

Francis R. Bach. 2013. Learning with submodular functions: A convex optimization perspective. Found. Trends Mach. Learn. 6, 2--3 (2013), 145--373.

Digital Library

[5]

Zsolt Baranyai. 1975. On the factorization of the complete uniform hypergraph. In Infinite and Finite Sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. 1. 91--108.

[6]

Alexandre Belloni, Tengyuan Liang, Hariharan Narayanan, and Alexander Rakhlin. 2015. Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Proceedings of the 28th Conference on Learning Theory, Peter Grünwald, Elad Hazan, and Satyen Kale (Eds.), Proceedings of Machine Learning Research, Vol. 40. 240--265.

[7]

Piotr Berman, Meiram Murzabulatov, and Sofya Raskhodnikova. 2016. Tolerant testers of image properties. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), LIPIcs, Vol. 55. Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, 90:1--90:14.

[8]

Eric Blais. 2008. Improved bounds for testing juntas. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer, Berlin, 317--330.

Digital Library

[9]

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

Digital Library

[10]

Eric Blais. 2012. Testing Properties of Boolean Functions. Ph.D. Dissertation. CMU.

Digital Library

[11]

Avrim L. Blum. 1994. Relevant examples and relevant features: Thoughts from computational learning theory. In Proceedings of the AAAI Fall Symposium on Relevance, Vol. 5.

[12]

Avrim L. Blum and Pat Langley. 1997. Selection of relevant features and examples in machine learning. Artif. Intell. 97, 1 (1997), 245--271.

Digital Library

[13]

Madeline V. Brandt. 2015. Intersecting Hypergraphs and Decompositions of Complete Uniform Hypergraphs. B.A. Thesis, Reed College.

[14]

Andrea Campagna, Alan Guo, and Ronitt Rubinfeld. 2013. Local reconstructors and tolerant testers for connectivity and diameter. In Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the International Conference on Randomization and Computation (APPROX-RANDOM’13), Lecture Notes in Computer Science, Vol. 8096. Springer, Berlin, 411--424.

[15]

Sourav Chakraborty, Eldar Fischer, David García-Soriano, and Arie Matsliah. 2012. Junto-symmetric functions, hypergraph isomorphism and crunching. In Proceedings of the Conference on Computational Complexity. IEEE, Los Alamitos, CA, 148--158.

Digital Library

[16]

Sourav Chakraborty, David García-Soriano, and Arie Matsliah. 2011. Efficient sample extractors for juntas with applications. InLecture Notes in Computer Science, Vol. 6755. Springer, Berlin, 545--556.

[17]

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

Digital Library

[18]

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, and Andrew Wan. 2007. Testing for concise representations. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS’07). IEEE, 549--558.

Digital Library

[19]

Shahar Fattal and Dana Ron. 2010. Approximating the distance to monotonicity in high dimensions. ACM Trans. Algor. 6, 3 (2010), 52.

Digital Library

[20]

Eldar Fischer and Lance Fortnow. 2006. Tolerant versus intolerant testing for Boolean properties. Theory Comput. 2, 9 (2006), 173--183.

[21]

Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, and Alex Samorodnitsky. 2004. Testing juntas. J. Comput. Syst. Sci. 68, 4 (2004), 753--787.

Digital Library

[22]

Eldar Fischer and Ilan Newman. 2007. Testing versus estimation of graph properties. SIAM J. Comput. 37, 2 (2007), 482--501.

Digital Library

[23]

Martin Grötschel, László Lovász, and Alexander Schrijver. 2012. Geometric Algorithms and Combinatorial Optimization. Vol. 2. Springer Science 8 Business Media.

[24]

Venkatesan Guruswami and Atri Rudra. 2005. Tolerant locally testable codes. In Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the International Conference on Randomization and Computation (APPROX-RANDOM’05), Lecture Notes in Computer Science, Vol. 3624. Springer, Berlin, 306--317.

Digital Library

[25]

Z. Q. John Lu. 2010. The elements of statistical learning: Data mining, inference, and prediction. J. Roy. Stat. Soc. Ser. A 173, 3 (2010), 693--694.

[26]

Michael Kearns and Dana Ron. 1998. Testing problems with sub-learning sample complexity. In Proceedings of the Annual Conference on Learning Theory (COLT’98). ACM, 268--279.

Digital Library

[27]

Swastik Kopparty and Shubhangi Saraf. 2009. Tolerant linearity testing and locally testable codes. In Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the International Conference on Randomization and Computation (APPROX-RANDOM’09), Lecture Notes in Computer Science, Vol. 5687. Springer, Berlin, 601--614.

Digital Library

[28]

Pravesh Kothari, Amir Nayyeri, Ryan O’Donnell, and Chenggang Wu. 2014. Testing surface area. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 1204--1214.

Digital Library

[29]

Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. 2015. A faster cutting plane method and its implications for combinatorial and convex optimization. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS’15). IEEE, 1049--1065.

Digital Library

[30]

Amit Levi and Erik Waingarten. 2018. Lower bounds for tolerant junta and unateness testing via rejection sampling of graphs. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS'19). 52:1--52:20.

[31]

Sharon Marko and Dana Ron. 2009. Approximating the distance to properties in bounded-degree and general sparse graphs. ACM Trans. Algorithms 5, 2 (2009).

Digital Library

[32]

Elchanan Mossel, Ryan O’Donnell, and Rocco P. Servedio. 2003. Learning juntas. In Proceedings of the Symposium on Theory of Computing (STOC’03). ACM, 206--212.

Digital Library

[33]

Michal Parnas and Dana Ron. 2002. Testing the diameter of graphs. Rand. Struct. Algor. 20, 2 (2002), 165--183.

Digital Library

[34]

Michal Parnas, Dana Ron, and Ronitt Rubinfeld. 2006. Tolerant property testing and distance approximation. J. Comput. Syst. Sci. 72, 6 (2006), 1012--1042.

Digital Library

[35]

Alexander Schrijver. 2002. Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24. Springer Science 8 Business Media.

[36]

Rocco A. Servedio, Li-Yang Tan, and John Wright. 2015. Adaptivity helps for testing juntas. In Proceedings of the Conference on Computational Complexity, LIPIcs, Vol. 33. Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, 264--279.

Digital Library

[37]

Zoya Svitkina and Lisa Fleischer. 2011. Submodular approximation: Sampling-based algorithms and lower bounds. SIAM J. Comput. 40, 6 (2011), 1715--1737.

Digital Library

[38]

Roei Tell. 2016. A note on tolerant testing with one-sided error. In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC’16), Vol. 23. 32.

[39]

Gregory Valiant. 2015. Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem. J. ACM 62, 2 (2015), 13.

Digital Library

Cited By

Cohen Sidon ORon D(2024)Sample-Based Distance-Approximation for Subsequence-FreenessAlgorithmica10.1007/s00453-024-01233-486:8(2519-2556)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00453-024-01233-4
Shapira AKushnir NGishboliner L(2024)Testing versus estimation of graph properties, revisitedRandom Structures & Algorithms10.1002/rsa.2122165:3(460-487)Online publication date: 26-Apr-2024
https://doi.org/10.1002/rsa.21221
Blanc GLange JMalik ATan LSaha BServedio R(2023)Lifting Uniform Learners via Distributional DecompositionProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585212(1755-1767)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585212
Show More Cited By

Index Terms

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
    2. Streaming, sublinear and near linear time algorithms

Recommendations

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 ...
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 ...
Tolerant junta testing and the connection to submodular optimization and function isomorphism
SODA '18: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

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

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computation Theory

ACM Transactions on Computation Theory Volume 11, Issue 4

December 2019

252 pages

ISSN:1942-3454

EISSN:1942-3462

DOI:10.1145/3331049

Editor:
Venkatesan Guruswami
Carnegie Mellon University, USA

Issue’s Table of Contents

Copyright © 2019 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: 22 July 2019

Accepted: 01 April 2019

Received: 01 February 2018

Published in TOCT Volume 11, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
143
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)3

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cohen Sidon ORon D(2024)Sample-Based Distance-Approximation for Subsequence-FreenessAlgorithmica10.1007/s00453-024-01233-486:8(2519-2556)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00453-024-01233-4
Shapira AKushnir NGishboliner L(2024)Testing versus estimation of graph properties, revisitedRandom Structures & Algorithms10.1002/rsa.2122165:3(460-487)Online publication date: 26-Apr-2024
https://doi.org/10.1002/rsa.21221
Blanc GLange JMalik ATan LSaha BServedio R(2023)Lifting Uniform Learners via Distributional DecompositionProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585212(1755-1767)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585212
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
Fiat NRon DMarx D(2021)On efficient distance approximation for graph propertiesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458162(1618-1637)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458162
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
Acharya JCanonne CTyagi H(2020)Inference Under Information Constraints I: Lower Bounds From Chi-Square ContractionIEEE Transactions on Information Theory10.1109/TIT.2020.302844066:12(7835-7855)Online publication date: 20-Nov-2020
https://dl.acm.org/doi/10.1109/TIT.2020.3028440
Acharya JCanonne CTyagi H(2020)Inference Under Information Constraints II: Communication Constraints and Shared RandomnessIEEE Transactions on Information Theory10.1109/TIT.2020.302843966:12(7856-7877)Online publication date: 20-Nov-2020
https://dl.acm.org/doi/10.1109/TIT.2020.3028439

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents