{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:46Z","timestamp":1750221166889,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,6,8]],"date-time":"2018-06-08T00:00:00Z","timestamp":1528416000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319206"],"award-info":[{"award-number":["CCF-1319206"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2018,9,30]]},"abstract":"\n Let\n \n X\n m,\u03b5<\/jats:sub>\n <\/jats:italic>\n be the distribution over\n m<\/jats:italic>\n bits\n X<\/jats:italic>\n 1<\/jats:sub>\n ,\u2026,\n X<\/jats:italic>\n \n m<\/jats:italic>\n <\/jats:sub>\n where the\n \n X\n i<\/jats:sub>\n <\/jats:italic>\n are independent and each\n \n X\n i<\/jats:sub>\n <\/jats:italic>\n equals 1 with probability (1\u2212\n \u03b5<\/jats:italic>\n )\/2 and 0 with probability (1 \u2212\n \u03b5<\/jats:italic>\n )\/2. We consider the smallest value\n \u03b5<\/jats:italic>\n *<\/jats:sup>\n of \u03b5 such that the distributions\n \n X\n m, \u03b5<\/jats:sub>\n <\/jats:italic>\n and\n \n X\n m, 0<\/jats:sub>\n <\/jats:italic>\n can be distinguished with constant advantage by a function\n f<\/jats:italic>\n : {0,1}\n m<\/jats:sup>\n \u2192\n S<\/jats:italic>\n , which is the product of\n k<\/jats:italic>\n functions\n f<\/jats:italic>\n 1<\/jats:sub>\n ,\n f<\/jats:italic>\n 2<\/jats:sub>\n ,\u2026,\n \n f\n k<\/jats:sub>\n <\/jats:italic>\n on disjoint inputs of\n n<\/jats:italic>\n bits, where each\n \n f\n i<\/jats:sub>\n <\/jats:italic>\n : {0,1}\n n<\/jats:sup>\n \u2192\n S<\/jats:italic>\n and\n m<\/jats:italic>\n =\n nk<\/jats:italic>\n .\n <\/jats:p>\n \n We prove that \u03b5\n *<\/jats:sup>\n = \u0398(1\/\u221a\n n<\/jats:italic>\n log\n k<\/jats:italic>\n ) if\n S<\/jats:italic>\n = [\u22121,1], while \u03b5\n *<\/jats:sup>\n = \u0398(1\/\u221a\n nk<\/jats:italic>\n ) if\n S<\/jats:italic>\n is the set of unit-norm complex numbers.\n <\/jats:p>","DOI":"10.1145\/3201787","type":"journal-article","created":{"date-parts":[[2018,6,11]],"date-time":"2018-06-11T12:20:54Z","timestamp":1528719654000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["The Coin Problem for Product Tests"],"prefix":"10.1145","volume":"10","author":[{"given":"Chin Ho","family":"Lee","sequence":"first","affiliation":[{"name":"Northeastern University"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[{"name":"Northeastern University"}]}],"member":"320","published-online":{"date-parts":[[2018,6,8]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/1806689.1806711"},{"volume-title":"Automata, Languages and Programming. Part I","author":"Aaronson Scott","series-title":"Lecture Notes in Computer Science","key":"e_1_2_1_2_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1016\/0168-0072(83)90038-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/28395.28410"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.5555\/874062.875534"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1109\/FOCS.2010.10"},{"volume-title":"Proceedings of the International Cryptology Conference (CRYPTO\u201913)","author":"Cohen Gil","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the Workshop on Randomization and Computation (RANDOM\u201914)","year":"2014","author":"Cohen Gil","key":"e_1_2_1_8_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1002\/(SICI)1098-2418(199808)13:1%3C1::AID-RSA1%3E3.0.CO;2-W"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1109\/FOCS.2015.60"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1109\/FOCS.2012.77"},{"key":"e_1_2_1_12_1","first-page":"19","article-title":"Inequalities and tail bounds for elementary symmetric polynomials","volume":"21","author":"Gopalan Parikshit","year":"2014","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.5555\/3135595.3135609"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1214\/aoms\/1177696958"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/195058.195190"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1007\/s004930200021"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1007\/BF01305237"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1006\/jcss.1996.0004"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1137\/080735096"},{"doi-asserted-by":"crossref","unstructured":"J. Michael Steele. 2004. The Cauchy-Schwarz Master Class. Mathematical Association of America Washington DC. J. Michael Steele. 2004. The Cauchy-Schwarz Master Class. Mathematical Association of America Washington DC.","key":"e_1_2_1_20_1","DOI":"10.1017\/CBO9780511817106"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1109\/CCC.2013.33"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1016\/0196-6774(84)90016-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1007\/s00037-013-0076-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1007\/s00037-012-0036-6"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3201787","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3201787","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3201787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:53Z","timestamp":1750208933000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3201787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,8]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9,30]]}},"alternative-id":["10.1145\/3201787"],"URL":"https:\/\/doi.org\/10.1145\/3201787","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2018,6,8]]},"assertion":[{"value":"2017-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}