{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,29]],"date-time":"2024-10-29T17:12:18Z","timestamp":1730221938621,"version":"3.28.0"},"reference-count":58,"publisher":"IEEE","license":[{"start":{"date-parts":[[2023,11,6]],"date-time":"2023-11-06T00:00:00Z","timestamp":1699228800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2023,11,6]],"date-time":"2023-11-06T00:00:00Z","timestamp":1699228800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,11,6]]},"DOI":"10.1109\/focs57990.2023.00107","type":"proceedings-article","created":{"date-parts":[[2023,12,22]],"date-time":"2023-12-22T19:20:35Z","timestamp":1703272835000},"page":"1757-1777","source":"Crossref","is-referenced-by-count":0,"title":["A strong composition theorem for junta complexity and the boosting of property testers"],"prefix":"10.1109","author":[{"given":"Guy","family":"Blanc","sequence":"first","affiliation":[{"name":"Stanford University,Stanford,USA"}]},{"given":"Caleb","family":"Koch","sequence":"additional","affiliation":[{"name":"Stanford University,Stanford,USA"}]},{"given":"Carmen","family":"Strassle","sequence":"additional","affiliation":[{"name":"Stanford University,Stanford,USA"}]},{"given":"Li-Yang","family":"Tan","sequence":"additional","affiliation":[{"name":"Stanford University,Stanford,USA"}]}],"member":"263","reference":[{"key":"ref1","first-page":"1","article-title":"Relevant examples and relevant features: Thoughts from computational learning theory","volume-title":"AAAI Fall Symposium on \u2018Relevance\u2019","volume":"5","author":"Blum"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00063-5"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45167-9_54"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1004"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.002"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.014"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-007-0061-6"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2310-z"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990277"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.16"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0099-2"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/2728167"},{"key":"ref13","first-page":"1946","article-title":"Learning and testing junta distributions","volume-title":"Conference on Learning Theory (COLT)","author":"Aliakbarpour"},{"key":"ref14","first-page":"1060","article-title":"Learning and testing junta distributions with sub cube conditioning","volume-title":"Conference on Learning Theory (COLT)","author":"Chen"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch43"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.004"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.01.023"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85363-3_26"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536437"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22006-7_46"},{"key":"ref21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/cjtcs.2013.006","article-title":"The non-adaptive query complexity of testing k-parities","volume":"6","author":"Buhrman","year":"2013","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"ref22","first-page":"264","article-title":"Adaptivity helps for testing juntas","volume-title":"Proceedings of the 30th Conference on Computational Complexity","author":"Servedio"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch65"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188784"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00095"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188842"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/3213772"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.138"},{"article-title":"Almost optimal distribution-free junta testing","volume-title":"34th Computational Complexity Conference (CCC)","author":"Bshouty","key":"ref29"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-19955-5_5"},{"article-title":"Lower bounds for tolerant junta and unateness testing via rejection sampling of graphs","volume-title":"Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS)","author":"Levi","key":"ref31"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00090"},{"article-title":"Junta distance approximation with sub-exponential queries","volume-title":"Proceedings of the 36th Computational Complexity Conference (CCC)","author":"Iyer","key":"ref33"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21029"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.32"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16367-8_11"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1561\/0400000029"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16367-8_4"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_709"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.45"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22185"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22670-0_23"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492584"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510015"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9781139814782"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101407444"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0040"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022949332276"},{"key":"ref50","article-title":"New lower bounds for adaptive tolerant junta testing","author":"Chen","year":"2023","journal-title":"arXiv preprint arXiv:2304.10647"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0043-7"},{"key":"ref52","first-page":"29:1","article-title":"Optimal Separation and Strong Direct Sum for Randomized Query Complexity","volume-title":"34th Computational Complexity Conference (CCC)","volume":"137","author":"Blais"},{"key":"ref53","article-title":"A strong XOR lemma for randomized query complexity","author":"Brody","year":"2020","journal-title":"arXiv preprint arXiv:2007.05580"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0175-x"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176346079"},{"key":"ref56","article-title":"Negative association: definition, properties, and applications","author":"Wajc","year":"2017","journal-title":"Manuscript"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.04.011"}],"event":{"name":"2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)","start":{"date-parts":[[2023,11,6]]},"location":"Santa Cruz, CA, USA","end":{"date-parts":[[2023,11,9]]}},"container-title":["2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/10353068\/10353072\/10353091.pdf?arnumber=10353091","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T20:21:18Z","timestamp":1705090878000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10353091\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,6]]},"references-count":58,"URL":"https:\/\/doi.org\/10.1109\/focs57990.2023.00107","relation":{},"subject":[],"published":{"date-parts":[[2023,11,6]]}}}