{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:09Z","timestamp":1750220889353,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T00:00:00Z","timestamp":1576454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["ERC-CoG grant 772839"],"award-info":[{"award-number":["ERC-CoG grant 772839"]}],"id":[{"id":"10.13039\/100010663","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":[[2020,3,31]]},"abstract":"<jats:p>\n            The direct product encoding of a string\n            <jats:italic>a<\/jats:italic>\n            \u2208 { 0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            on an underlying domain\n            <jats:italic>V<\/jats:italic>\n            \u2286 (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              [\n              <jats:italic>n<\/jats:italic>\n              ]\n            <\/jats:sup>\n            ) is a function DP\n            <jats:sub>\n              <jats:italic>V<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>a<\/jats:italic>\n            ) that gets as input a set\n            <jats:italic>S<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            and outputs\n            <jats:italic>a<\/jats:italic>\n            restricted to\n            <jats:italic>S<\/jats:italic>\n            . In the direct product testing problem, we are given a function\n            <jats:italic>F<\/jats:italic>\n            :\n            <jats:italic>V<\/jats:italic>\n            \u2192 { 0,1}\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            , and our goal is to test whether\n            <jats:italic>F<\/jats:italic>\n            is close to a direct product encoding\u2014that is, whether there exists some\n            <jats:italic>a<\/jats:italic>\n            \u2208 { 0,1}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            such that on most sets\n            <jats:italic>S<\/jats:italic>\n            , we have\n            <jats:italic>F<\/jats:italic>\n            (\n            <jats:italic>S<\/jats:italic>\n            )=DP\n            <jats:sub>\n              <jats:italic>V<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>a<\/jats:italic>\n            )(\n            <jats:italic>S<\/jats:italic>\n            ). A natural test is as follows: select a pair (\n            <jats:italic>S<\/jats:italic>\n            ,\n            <jats:italic>S<\/jats:italic>\n            \u2032)\u2208\n            <jats:italic>V<\/jats:italic>\n            according to some underlying distribution over\n            <jats:italic>V<\/jats:italic>\n            \u00d7\n            <jats:italic>V<\/jats:italic>\n            , query\n            <jats:italic>F<\/jats:italic>\n            on this pair, and check for consistency on their intersection. Note that the preceding distribution may be viewed as a weighted graph over the vertex set\n            <jats:italic>V<\/jats:italic>\n            and is referred to as a test graph.\n          <\/jats:p>\n          <jats:p>\n            The testability of direct products was studied over various domains and test graphs: Dinur and Steurer (CCC\u201914) analyzed it when\n            <jats:italic>V<\/jats:italic>\n            equals the\n            <jats:italic>k<\/jats:italic>\n            -th slice of the Boolean hypercube and the test graph is a member of the Johnson graph family. Dinur and Kaufman (FOCS\u201917) analyzed it for the case where\n            <jats:italic>V<\/jats:italic>\n            is the set of faces of a Ramanujan complex, where in this case \u2223\n            <jats:italic>V<\/jats:italic>\n            \u2223=\n            <jats:italic>O<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            ). In this article, we study the testability of direct products in a general setting, addressing the question: what properties of the domain and the test graph allow one to prove a direct product testing theorem?\n          <\/jats:p>\n          <jats:p>\n            Towards this goal, we introduce the notion of coordinate expansion of a test graph. Roughly speaking, a test graph is a coordinate expander if it has global and local expansion, and has certain nice intersection properties on sampling. We show that whenever the test graph has coordinate expansion, it admits a direct product testing theorem. Additionally, for every\n            <jats:italic>k<\/jats:italic>\n            and\n            <jats:italic>n<\/jats:italic>\n            , we provide a direct product domain\n            <jats:italic>V<\/jats:italic>\n            \u2286 (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            ) of size\n            <jats:italic>n<\/jats:italic>\n            , called the\n            <jats:italic>sliding window domain<\/jats:italic>\n            , for which we prove direct product testability.\n          <\/jats:p>","DOI":"10.1145\/3369939","type":"journal-article","created":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T13:32:58Z","timestamp":1576589578000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Toward a General Direct Product Testing Theorem"],"prefix":"10.1145","volume":"12","author":[{"given":"Elazar","family":"Goldenberg","sequence":"first","affiliation":[{"name":"Academic College of Tel Aviv\u2013Yaffo, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karthik","family":"C. S.","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,12,16]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/258533.258642"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917)","author":"Bhangale Amey","year":"2017","unstructured":"Amey Bhangale , Irit Dinur , and Inbal Livni Navon . 2017 . Cube vs. cube low degree test . In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917) . Article 40, 31 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ITCS. 2017.40 10.4230\/LIPIcs.ITCS.2017.40 Amey Bhangale, Irit Dinur, and Inbal Livni Navon. 2017. Cube vs. cube low degree test. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917). Article 40, 31 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2017.40"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1016\/j.jctb.2018.04.005"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1137\/16M1061655"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1109\/FOCS.2008.26"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1137\/1.9781611975482.129"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1109\/FOCS.2017.94"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/3188745.3188806"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.5555\/3135595.3135624"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1137\/S0097539705446962"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1109\/CCC.2014.27"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1137\/S0097539797315744"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1137\/09077299X"},{"key":"e_1_2_1_14_1","first-page":"78","article-title":"Small set expansion in the Johnson graph","volume":"25","author":"Khot Subhash","year":"2018","unstructured":"Subhash Khot , Dor Minzer , Dana Moshkovitz , and Muli Safra . 2018 . Small set expansion in the Johnson graph . Electronic Colloquium on Computational Complexity 25 (2018), 78 . https:\/\/eccc.weizmann.ac.il\/report\/2018\/078. Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra. 2018. Small set expansion in the Johnson graph. Electronic Colloquium on Computational Complexity 25 (2018), 78. https:\/\/eccc.weizmann.ac.il\/report\/2018\/078.","journal-title":"Electronic Colloquium on Computational Complexity"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/258533.258641"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369939","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3369939","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:27Z","timestamp":1750203867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369939"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,16]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3369939"],"URL":"https:\/\/doi.org\/10.1145\/3369939","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,12,16]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}