{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:27Z","timestamp":1750220967667,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,7,11]],"date-time":"2019-07-11T00:00:00Z","timestamp":1562803200000},"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"}]},{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]}],"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            For a test\n            <jats:italic>T<\/jats:italic>\n            \u2286 {0, 1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            , define\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            (\n            <jats:italic>T<\/jats:italic>\n            ) to be the maximum\n            <jats:italic>k<\/jats:italic>\n            such that there exists a\n            <jats:italic>k<\/jats:italic>\n            -wise uniform distribution over {0, 1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            whose support is a subset of\n            <jats:italic>T<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            For\n            <jats:italic>\n              H\n              <jats:sub>t<\/jats:sub>\n            <\/jats:italic>\n            = {\n            <jats:italic>x<\/jats:italic>\n            \u2208 {0, 1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            : | \u2211\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>\n              x\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            \u2212\n            <jats:italic>n<\/jats:italic>\n            \/2| \u2264\n            <jats:italic>t<\/jats:italic>\n            }, we prove\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            (\n            <jats:italic>\n              H\n              <jats:sub>t<\/jats:sub>\n            <\/jats:italic>\n            ) = \u0398 (\n            <jats:italic>t<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/\n            <jats:italic>n<\/jats:italic>\n            + 1).\n          <\/jats:p>\n          <jats:p>\n            For\n            <jats:italic>\n              S\n              <jats:sub>m, c<\/jats:sub>\n            <\/jats:italic>\n            = {\n            <jats:italic>x<\/jats:italic>\n            \u2208 {0, 1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            : \u2211\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            <jats:italic>\n              x\n              <jats:sub>i<\/jats:sub>\n            <\/jats:italic>\n            \u2261\n            <jats:italic>c<\/jats:italic>\n            (mod\n            <jats:italic>m<\/jats:italic>\n            )}, we prove that\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            (\n            <jats:italic>\n              S\n              <jats:sub>m, c<\/jats:sub>\n            <\/jats:italic>\n            ) = \u0398 (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ). For some\n            <jats:italic>k<\/jats:italic>\n            =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>m<\/jats:italic>\n            ) we also show that any\n            <jats:italic>k<\/jats:italic>\n            -wise uniform distribution puts probability mass at most 1\/\n            <jats:italic>m<\/jats:italic>\n            + 1\/100 over\n            <jats:italic>\n              S\n              <jats:sub>m, c<\/jats:sub>\n            <\/jats:italic>\n            . Finally, for any fixed odd\n            <jats:italic>m<\/jats:italic>\n            we show that there is an integer\n            <jats:italic>k<\/jats:italic>\n            = (1 \u2212 \u03a9(1))\n            <jats:italic>n<\/jats:italic>\n            such that any\n            <jats:italic>k<\/jats:italic>\n            -wise uniform distribution lands in\n            <jats:italic>T<\/jats:italic>\n            with probability exponentially close to |\n            <jats:italic>\n              S\n              <jats:sub>m, c<\/jats:sub>\n            <\/jats:italic>\n            |\/2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            ; and this result is false for any even\n            <jats:italic>m<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3337783","type":"journal-article","created":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T13:12:41Z","timestamp":1562937161000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Bounded Independence versus Symmetric Tests"],"prefix":"10.1145","volume":"11","author":[{"given":"Ravi","family":"Boppana","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}]},{"given":"Johan","family":"H\u00e5stad","sequence":"additional","affiliation":[{"name":"KTH-Royal Institute of Technology"}]},{"given":"Chin Ho","family":"Lee","sequence":"additional","affiliation":[{"name":"Northeastern University, Huntington Avenue, West Village H, Boston, MA"}]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[{"name":"Northeastern University, Huntington Avenue, West Village H, Boston, MA"}]}],"member":"320","published-online":{"date-parts":[[2019,7,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Deterministic simulation of probabilistic constant-depth circuits. Advances in Computing Research\u2014Randomness and Computation 5","author":"Ajtai Miklos","year":"1989","unstructured":"Miklos Ajtai and Avi Wigderson . 1989. Deterministic simulation of probabilistic constant-depth circuits. Advances in Computing Research\u2014Randomness and Computation 5 ( 1989 ), 199--223. Miklos Ajtai and Avi Wigderson. 1989. Deterministic simulation of probabilistic constant-depth circuits. Advances in Computing Research\u2014Randomness and Computation 5 (1989), 199--223."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00359-4"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/070691954"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055423"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 20th International Workshop on Randomization and Computation (RANDOM\u201916), Leibniz International Proceedings in Informatics","volume":"60","author":"Boppana Ravi","year":"2016","unstructured":"Ravi Boppana , Johan H\u00e5stad , Chin Ho Lee , and Emanuele Viola . 2016 . Bounded independence vs. moduli . In Proceedings of the 20th International Workshop on Randomization and Computation (RANDOM\u201916), Leibniz International Proceedings in Informatics , Vol. 60 . Schloss Dagstuhl, 24:1--24:9. Ravi Boppana, Johan H\u00e5stad, Chin Ho Lee, and Emanuele Viola. 2016. Bounded independence vs. moduli. In Proceedings of the 20th International Workshop on Randomization and Computation (RANDOM\u201916), Leibniz International Proceedings in Informatics, Vol. 60. Schloss Dagstuhl, 24:1--24:9."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754401"},{"key":"e_1_2_1_7_1","unstructured":"Neal Carothers. {n.d.}. A Short Course on Approximation Theory. Retrieved from http:\/\/fourier.math.uoc.gr\/&sim;mk\/approx1011\/carothers.pdf.  Neal Carothers. {n.d.}. A Short Course on Approximation Theory. Retrieved from http:\/\/fourier.math.uoc.gr\/&sim;mk\/approx1011\/carothers.pdf."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1695"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897528"},{"volume-title":"Introduction to Approximation Theory","author":"Cheney Elliott","key":"e_1_2_1_11_1","unstructured":"Elliott Cheney . 1966. Introduction to Approximation Theory . McGraw-Hill , New York, NY . Elliott Cheney. 1966. Introduction to Approximation Theory. McGraw-Hill, New York, NY."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/100783030"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129714"},{"key":"e_1_2_1_15_1","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller William","unstructured":"William Feller . 1971. An Introduction to Probability Theory and Its Applications ( 2 nd ed.). Vol. 2 . Wiley . William Feller. 1971. An Introduction to Probability Theory and Its Applications (2nd ed.). Vol. 2. Wiley.","edition":"2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.77"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.29"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4064\/sm-70-3-231-283"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1129088"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 20th International Workshop on Randomization and Computation (RANDOM\u201916), Leibniz International Proceedings in Informatics","volume":"60","author":"Harsha Prahladh","year":"2016","unstructured":"Prahladh Harsha and Srikanth Srinivasan . 2016 . On polynomial approximations to AC<sup>0<\/sup> . In Proceedings of the 20th International Workshop on Randomization and Computation (RANDOM\u201916), Leibniz International Proceedings in Informatics , Vol. 60 . Schloss Dagstuhl, 32:1--32:14. Prahladh Harsha and Srikanth Srinivasan. 2016. On polynomial approximations to AC<sup>0<\/sup>. In Proceedings of the 20th International Workshop on Randomization and Computation (RANDOM\u201916), Leibniz International Proceedings in Informatics, Vol. 60. Schloss Dagstuhl, 32:1--32:14."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192399"},{"key":"e_1_2_1_22_1","unstructured":"Chin Ho Lee and Emanuele Viola. 2017. More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. Retreived from http:\/\/www.ccs.neu.edu\/home\/viola\/.  Chin Ho Lee and Emanuele Viola. 2017. More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. Retreived from http:\/\/www.ccs.neu.edu\/home\/viola\/."},{"key":"e_1_2_1_23_1","volume-title":"Article 16","author":"Lee Chin Ho","year":"2017","unstructured":"Chin Ho Lee and Emanuele Viola . 2017. Some limitations of the sum of small-bias distributions. Theory Comput. 13 , Article 16 ( 2017 ), 23 pages. Chin Ho Lee and Emanuele Viola. 2017. Some limitations of the sum of small-bias distributions. Theory Comput. 13, Article 16 (2017), 23 pages."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_49"},{"volume-title":"Analysis of Boolean Functions","author":"O\u2019Donnell Ryan","key":"e_1_2_1_25_1","unstructured":"Ryan O\u2019Donnell . 2014. Analysis of Boolean Functions . Cambridge University Press . Ryan O\u2019Donnell. 2014. Analysis of Boolean Functions. Cambridge University Press."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/090764190"},{"key":"e_1_2_1_27_1","first-page":"598","article-title":"Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function","volume":"41","author":"Razborov Alexander A.","year":"1987","unstructured":"Alexander A. Razborov . 1987 . Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function . Akad. Nauk SSSR. Mat. Zamet. 41 , 4 (1987), 598 -- 607 . Alexander A. Razborov. 1987. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Akad. Nauk SSSR. Mat. Zamet. 41, 4 (1987), 598--607.","journal-title":"Akad. Nauk SSSR. Mat. Zamet."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490273"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/2308012"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 32nd Computational Complexity Conference. LIPIcs. Leibniz Int. Proc. Inform.","volume":"79","author":"Tal Avishay","year":"2017","unstructured":"Avishay Tal . 2017 . Tight bounds on the Fourier spectrum of AC<sup>0<\/sup> . In Proceedings of the 32nd Computational Complexity Conference. LIPIcs. Leibniz Int. Proc. Inform. , Vol. 79 . Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 15:1--15:31. Avishay Tal. 2017. Tight bounds on the Fourier spectrum of AC<sup>0<\/sup>. In Proceedings of the 32nd Computational Complexity Conference. LIPIcs. Leibniz Int. Proc. Inform., Vol. 79. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 15:1--15:31."},{"key":"e_1_2_1_32_1","unstructured":"Emanuele Viola. 2017. Special topics in complexity theory. Lecture notes of the class taught at Northeastern University. Retrieved from http:\/\/www.ccs.neu.edu\/home\/viola\/classes\/spepf17.html.  Emanuele Viola. 2017. Special topics in complexity theory. Lecture notes of the class taught at Northeastern University. Retrieved from http:\/\/www.ccs.neu.edu\/home\/viola\/classes\/spepf17.html."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a007"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3337783","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3337783","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3337783","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\/3337783"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,11]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3337783"],"URL":"https:\/\/doi.org\/10.1145\/3337783","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,7,11]]},"assertion":[{"value":"2018-05-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-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}