{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,21]],"date-time":"2025-06-21T08:02:47Z","timestamp":1750492967767,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,7,22]],"date-time":"2019-07-22T00:00:00Z","timestamp":1563753600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            A function\n            <jats:italic>f<\/jats:italic>\n            :{ \u22121,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u2192 { \u22121,1} is a\n            <jats:italic>k<\/jats:italic>\n            -junta if it depends on at most\n            <jats:italic>k<\/jats:italic>\n            of its variables. We consider the problem of\n            <jats:italic>tolerant<\/jats:italic>\n            testing of\n            <jats:italic>k<\/jats:italic>\n            -juntas, where the testing algorithm must accept any function that is \u03b5-\n            <jats:italic>close<\/jats:italic>\n            to some\n            <jats:italic>k<\/jats:italic>\n            -junta and reject any function that is \u03b5\u2032-far from every\n            <jats:italic>k<\/jats:italic>\n            \u2032-junta for some \u03b5\u2032 =\n            <jats:italic>O<\/jats:italic>\n            (\u03b5) and\n            <jats:italic>k<\/jats:italic>\n            \u2032 =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            Our first result is an algorithm that solves this problem with query complexity polynomial in\n            <jats:italic>k<\/jats:italic>\n            and 1\/\u03b5. This result is obtained via a new polynomial-time approximation algorithm for\n            <jats:italic>submodular function minimization<\/jats:italic>\n            (SFM) under large cardinality constraints, which holds even when only given an approximate oracle access to the function.\n          <\/jats:p>\n          <jats:p>\n            Our second result considers the case where\n            <jats:italic>k<\/jats:italic>\n            \u2032 =\n            <jats:italic>k<\/jats:italic>\n            . 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 \u03c1 \u2208 (0,1), accepts any function that is \u03b5 \u03c1\/16-close to some\n            <jats:italic>k<\/jats:italic>\n            -junta and rejects any function that is \u03b5-far from every\n            <jats:italic>k<\/jats:italic>\n            -junta. The query complexity of the algorithm is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            log\n            <jats:italic>k<\/jats:italic>\n            \/\u03b5 \u03c1 (1-\u03c1)\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            .\n          <\/jats:p>\n          <jats:p>\n            Finally, we show how to apply the second result to the problem of tolerant isomorphism testing between two unknown Boolean functions\n            <jats:italic>f<\/jats:italic>\n            and\n            <jats:italic>g<\/jats:italic>\n            . We give an algorithm for this problem whose query complexity only depends on the (unknown) smallest\n            <jats:italic>k<\/jats:italic>\n            such that either\n            <jats:italic>f<\/jats:italic>\n            or\n            <jats:italic>g<\/jats:italic>\n            is\n            <jats:italic>close<\/jats:italic>\n            to being a\n            <jats:italic>k<\/jats:italic>\n            -junta.\n          <\/jats:p>","DOI":"10.1145\/3337789","type":"journal-article","created":{"date-parts":[[2019,7,22]],"date-time":"2019-07-22T12:15:03Z","timestamp":1563797703000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism"],"prefix":"10.1145","volume":"11","author":[{"given":"Eric","family":"Blais","sequence":"first","affiliation":[{"name":"University of Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7153-5211","authenticated-orcid":false,"given":"Cl\u00e9ment L.","family":"Canonne","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Talya","family":"Eden","sequence":"additional","affiliation":[{"name":"School of EE, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Levi","sequence":"additional","affiliation":[{"name":"University of Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6576-7200","authenticated-orcid":false,"given":"Dana","family":"Ron","sequence":"additional","affiliation":[{"name":"School of EE, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,7,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286500.1286503"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886521.1886553"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832677"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2602000"},{"key":"e_1_2_1_5_1","volume-title":"Infinite and Finite Sets (Colloq.","author":"Baranyai Zsolt","year":"1975","unstructured":"Zsolt Baranyai . 1975 . On the factorization of the complete uniform hypergraph . In Infinite and Finite Sets (Colloq. , Keszthely , 1973; dedicated to P. Erd\u0151s on his 60th birthday), Vol. 1. 91--108. Zsolt Baranyai. 1975. On the factorization of the complete uniform hypergraph. In Infinite and Finite Sets (Colloq., Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday), Vol. 1. 91--108."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 28th Conference on Learning Theory, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.), Proceedings of Machine Learning Research","volume":"40","author":"Belloni Alexandre","year":"2015","unstructured":"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\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.), Proceedings of Machine Learning Research , Vol. 40 . 240--265. 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\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.), Proceedings of Machine Learning Research, Vol. 40. 240--265."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), LIPIcs","volume":"55","author":"Berman Piotr","year":"2016","unstructured":"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. 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."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_26"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536437"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the AAAI Fall Symposium on Relevance","volume":"5","author":"Blum Avrim L.","year":"1994","unstructured":"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 . 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."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00063-5"},{"volume-title":"Intersecting Hypergraphs and Decompositions of Complete Uniform Hypergraphs. B.A. Thesis","author":"Brandt Madeline V.","key":"e_1_2_1_13_1","unstructured":"Madeline V. Brandt . 2015. Intersecting Hypergraphs and Decompositions of Complete Uniform Hypergraphs. B.A. Thesis , Reed College . Madeline V. Brandt. 2015. Intersecting Hypergraphs and Decompositions of Complete Uniform Hypergraphs. B.A. Thesis, Reed College."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_29"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.28"},{"volume-title":"Efficient sample extractors for juntas with applications. InLecture Notes in Computer Science","author":"Chakraborty Sourav","key":"e_1_2_1_16_1","unstructured":"Sourav Chakraborty , David Garc\u00eda-Soriano , and Arie Matsliah . 2011. Efficient sample extractors for juntas with applications. InLecture Notes in Computer Science , Vol. 6755 . Springer , Berlin , 545--556. Sourav Chakraborty, David Garc\u00eda-Soriano, and Arie Matsliah. 2011. Efficient sample extractors for juntas with applications. InLecture Notes in Computer Science, Vol. 6755. Springer, Berlin, 545--556."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.023"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.70"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798605"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a009"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.004"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/060652324"},{"volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin","key":"e_1_2_1_23_1","unstructured":"Martin Gr\u00f6tschel , L\u00e1szl\u00f3 Lov\u00e1sz , and Alexander Schrijver . 2012. Geometric Algorithms and Combinatorial Optimization . Vol. 2 . Springer Science 8 Business Media. Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 2012. Geometric Algorithms and Combinatorial Optimization. Vol. 2. Springer Science 8 Business Media."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_26"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-985X.2010.00646_6.x"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/279943.279996"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_45"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634163"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.68"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS'19)","author":"Levi Amit","year":"2018","unstructured":"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. 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."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1497290.1497298"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780574"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10013.abs"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.03.002"},{"key":"e_1_2_1_35_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency.","author":"Schrijver Alexander","year":"2002","unstructured":"Alexander Schrijver . 2002 . Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24 . Springer Science 8 Business Media. Alexander Schrijver. 2002. Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24. Springer Science 8 Business Media."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the Conference on Computational Complexity, LIPIcs","volume":"33","author":"Servedio Rocco A.","year":"2015","unstructured":"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. 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."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783352"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Electronic Colloquium on Computational Complexity (ECCC\u201916)","volume":"23","author":"Tell Roei","year":"2016","unstructured":"Roei Tell . 2016 . A note on tolerant testing with one-sided error . In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC\u201916) , Vol. 23 . 32. Roei Tell. 2016. A note on tolerant testing with one-sided error. In Proceedings of the Electronic Colloquium on Computational Complexity (ECCC\u201916), Vol. 23. 32."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2728167"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3337789","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3337789","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:25Z","timestamp":1750204465000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3337789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,22]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3337789"],"URL":"https:\/\/doi.org\/10.1145\/3337789","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,7,22]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}