{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:00:17Z","timestamp":1750309217104,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2018,11,26]],"date-time":"2018-11-26T00:00:00Z","timestamp":1543190400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1703925, CCF-1420349, CCF-1563155 and CCF-1563122"],"award-info":[{"award-number":["CCF-1703925, CCF-1420349, CCF-1563155 and CCF-1563122"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF Graduate Research Fellowship","award":["DGE-16-44869"],"award-info":[{"award-number":["DGE-16-44869"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>\n            We prove that any non-adaptive algorithm that tests whether an unknown Boolean function\n            <jats:italic>f<\/jats:italic>\n            :{0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u2192 {0,1} is a\n            <jats:italic>k<\/jats:italic>\n            -junta or \u03f5-far from every\n            <jats:italic>k<\/jats:italic>\n            -junta must make \u03a9\n            <jats:sup>\u02dc<\/jats:sup>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ) \/ \u03f5) many queries for a wide range of parameters\n            <jats:italic>k<\/jats:italic>\n            and \u03f5. Our result dramatically improves previous lower bounds and is essentially optimal since there is a known non-adaptive junta tester which makes \u03a9\n            <jats:sup>\u02dc<\/jats:sup>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>3\/2<\/jats:sup>\n            ) \/ \u03f5 queries. Combined with the known existence of an adaptive tester which makes\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            log\n            <jats:italic>k<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            \/\u03f5) queries, our result shows that adaptivity enables polynomial savings in query complexity for junta testing.\n          <\/jats:p>","DOI":"10.1145\/3213772","type":"journal-article","created":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T13:18:59Z","timestamp":1543324739000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Settling the Query Complexity of Non-adaptive Junta Testing"],"prefix":"10.1145","volume":"65","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[{"name":"Columbia University, Chicago, Illinois, USA"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, Chicago, Illinois, USA"}]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute, USA"}]},{"given":"Erik","family":"Waingarten","sequence":"additional","affiliation":[{"name":"Columbia University, Chicago, Illinois, USA"}]},{"given":"Jinyu","family":"Xie","sequence":"additional","affiliation":[{"name":"Columbia University, Chicago, Illinois, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,11,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1155\/JIA\/2006\/64307"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.856958"},{"key":"e_1_2_1_3_1","volume-title":"Testing unateness of real-valued functions. CoRR abs\/1608.07652","author":"Baleshzar Roksana","year":"2016","unstructured":"Roksana Baleshzar , Meiram Murzabulatov , Ramesh Krishnan S. Pallavoor , and Sofya Raskhodnikova . 2016. Testing unateness of real-valued functions. CoRR abs\/1608.07652 ( 2016 ). Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor, and Sofya Raskhodnikova. 2016. Testing unateness of real-valued functions. CoRR abs\/1608.07652 (2016)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897567"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0115129"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.54"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_26"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536437"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.31"},{"volume-title":"Proceedings of the 16th International Workshop on Randomization (RANDOM'12)","author":"Blais Eric","key":"e_1_2_1_10_1","unstructured":"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. 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."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_12_1","first-page":"1","article-title":"The non-adaptive query complexity of testing k-parities","volume":"06","author":"Buhrman Harry","year":"2013","unstructured":"Harry Buhrman , David Garc\u00eda-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 . Harry Buhrman, David Garc\u00eda-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.","journal-title":"Chicago J. Theor. Comput. Sci. Article"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488660"},{"key":"e_1_2_1_14_1","unstructured":"Deeparnab Chakrabarty and C. Seshadhri. 2016. A \u00d5(n) non-adaptive tester for unateness. CoRR abs\/1608.06980 (2016).  Deeparnab Chakrabarty and C. Seshadhri. 2016. A \u00d5( n ) non-adaptive tester for unateness. CoRR abs\/1608.06980 (2016)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746570"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.38"},{"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":"crossref","unstructured":"D. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press Cambridge.   D. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press Cambridge.","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.004"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(83)90038-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1980617"},{"volume-title":"Introduction to Property Testing","author":"Goldreich Oded","key":"e_1_2_1_24_1","unstructured":"Oded Goldreich . 2017. Introduction to Property Testing . Cambridge University Press . Oded Goldreich. 2017. Introduction to Property Testing. Cambridge University Press."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/100785429"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0112012"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90058-3"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.13"},{"key":"e_1_2_1_30_1","unstructured":"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.  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."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1964.11992272"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958029"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_48"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101407444"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000004"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000029"},{"volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'13)","author":"Ron D.","key":"e_1_2_1_37_1","unstructured":"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. 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."},{"key":"e_1_2_1_39_1","first-page":"328","article-title":"Binomial approximation to the Poisson binomial distribution: The Krawtchouk expansion","volume":"45","author":"Roos B.","year":"2000","unstructured":"B. Roos . 2000 . Binomial approximation to the Poisson binomial distribution: The Krawtchouk expansion . Theory Probab. Appl. 45 , 2 (2000), 328 -- 344 . B. Roos. 2000. Binomial approximation to the Poisson binomial distribution: The Krawtchouk expansion. Theory Probab. Appl. 45, 2 (2000), 328--344.","journal-title":"Theory Probab. Appl."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2833227.2833240"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3213772","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3213772","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3213772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:43:54Z","timestamp":1750290234000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3213772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,26]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3213772"],"URL":"https:\/\/doi.org\/10.1145\/3213772","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2018,11,26]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}