{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:31:01Z","timestamp":1787340661946,"version":"build-2736575974"},"reference-count":35,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2041920"],"award-info":[{"award-number":["CCF-2041920"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2402571"],"award-info":[{"award-number":["CCF-2402571"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2023495"],"award-info":[{"award-number":["DMS-2023495"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1740850"],"award-info":[{"award-number":["CCF-1740850"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1839317"],"award-info":[{"award-number":["1839317"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1813165"],"award-info":[{"award-number":["1813165"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1908384"],"award-info":[{"award-number":["1908384"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1909790"],"award-info":[{"award-number":["1909790"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2402572"],"award-info":[{"award-number":["2402572"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Monotonicity testing of Boolean functions on the hypergrid, [Formula: see text], is a classic topic in property testing. Determining the nonadaptive complexity of this problem is an important open question. For arbitrary [Formula: see text], [H. Black, D. Chakrabarty, and C. Seshadhri, Proceedings of the 14 th Annual ACM-SIAM Symposium on Discrete Algorithms, 2020, pp. 1975\u20131994]\u00a0describes a tester with query complexity [Formula: see text]. This complexity is independent of [Formula: see text] but has a suboptimal dependence on [Formula: see text]. Recently, Braverman et al. [ Proceedings of Innovations in Theoretical Computer Science, 2023, pp. 25:1\u201325:24] and H. Black, D. Chakrabarty, and C. Seshadhri [ Proceedings of the 55 th Annual ACM Symposium on Theory of Computing, 2023, pp. 233\u2013241] described [Formula: see text]- and [Formula: see text]-query testers, respectively. These testers have an almost optimal dependence on [Formula: see text] but a suboptimal polynomial dependence on [Formula: see text]. In this paper, we describe a nonadaptive, one-sided monotonicity tester with query complexity [Formula: see text] , independent of [Formula: see text]. Up to the [Formula: see text]-factors, our result resolves the nonadaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of [Formula: see text] yields a nonadaptive, one-sided [Formula: see text]-query monotonicity tester for Boolean functions [Formula: see text] associated with an arbitrary product measure.<\/jats:p>","DOI":"10.1137\/24m163339x","type":"journal-article","created":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T04:01:03Z","timestamp":1748577663000},"page":"FOCS23-147-FOCS23-191","source":"Crossref","is-referenced-by-count":0,"title":["A \\({d}^{{1\/2+{o}(1)}}\\) Monotonicity Tester for Boolean Functions on \\({d}\\)-Dimensional Hypergrids"],"prefix":"10.1137","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-9662-2870","authenticated-orcid":true,"given":"Hadley","family":"Black","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California San Diego, La Jolla, CA 92093 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Deeparnab","family":"Chakrabarty","sequence":"additional","affiliation":[{"name":"Computer Science, Dartmouth College, Hanover, NH 03755 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA 95064 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,5,30]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.06.001"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20167"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/16M1097006"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0040-x"},{"key":"ref5","unstructured":"H. Black, D. Chakrabarty, and C. Seshadhri, A \\(o(d)\\cdot \\textrm{polylog}(n)\\) monotonicity tester for Boolean functions over the hypergrid \\([n]^d\\), in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2018."},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"H. Black, D. Chakrabarty, and C. Seshadhri, Domain reduction: A \\(o(d)\\) tester for Boolean functions in \\(d\\)-dimensions, in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2020, pp. 1975\u20131994.","DOI":"10.1137\/1.9781611975994.122"},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"H. Black, D. Chakrabarty, and C. Seshadhri, Directed isoperimetric theorems for Boolean functions on the hypergrid and an \\(\\widetilde {O}(n\\sqrt {d})\\) monotonicity tester, in Proceedings of the ACM Symposium on Theory of Computing, 2023.","DOI":"10.1145\/3564246.3585167"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2765-1"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/100808186"},{"key":"ref10","unstructured":"A. Bhattacharyya, A Note on the Distance to Monotonicity of Boolean Functions, Technical Report 012, Electronic Colloquium on Computational Complexity, 2008."},{"key":"ref11","unstructured":"M. Braverman, S. Khot, G. Kindler, and D. Minzer, Improved monotonicity testers via hypercube embeddings, in Proceedings of Innovations in Theoretical Computer Science, 2023, pp. 25:1\u201325:24."},{"key":"ref12","unstructured":"H. Black, I. Kalemaj, and S. Raskhodnikova, Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing, https:\/\/doi.org\/10.48550\/arXiv.2011.09441, 2020."},{"key":"ref13","unstructured":"P. Berman, S. Raskhodnikova, and G. Yaroslavtsev, \\({L}_p\\)-testing, in Proceedings of the ACM Symposium on Theory of Computing, 2014."},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"E. Blais, S. Raskhodnikova, and G. Yaroslavtsev, Lower bounds for testing properties of functions over hypergrid domains, in Proceedings of the IEEE Conference on Computational Complexity, 2014.","DOI":"10.1109\/CCC.2014.38"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/3039241"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"X. Chen, A. De, R. A. Servedio, and L.Y. Tan, Boolean function monotonicity testing requires (almost) \\({O}(n^{1\/2})\\) non-adaptive queries, in Proceedings of the ACM Symposium on Theory of Computing, 2015.","DOI":"10.1145\/2746539.2746570"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"D. Chakrabarty and C. Seshadhri, Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids, in Proceedings of the ACM Symposium on Theory of Computing, 2013.","DOI":"10.1145\/2488608.2488661"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/13092770X"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"X. Chen, R. A. Servedio, and L.Y. Tan, New algorithms and lower bounds for monotonicity testing, in Proceedings of the IEEE Symposium on Foundations of Computer Science, 2014.","DOI":"10.1109\/FOCS.2014.38"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"X. Chen, E. Waingarten, and J. Xie, Beyond Talagrand: New lower bounds for testing monotonicity and unateness, in Proceedings of the ACM Symposium on Theory of Computing, 2017.","DOI":"10.1145\/3055399.3055461"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky, Improved testing algorithms for monotonicity, in Proceedings of the International Workshop on Randomization and Computation, 1999.","DOI":"10.1007\/978-3-540-48413-4_10"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1692"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.003"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, and R. Rubinfeld, Monotonicity testing over general poset domains, in Proceedings of the ACM Symposium on Theory of Computing, 2002.","DOI":"10.1145\/509907.509977"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798605"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070011"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"S. Halevy and E. Kushilevitz, Distribution-free property testing, in Proceedings of the International Workshop on Randomization and Computation, 2003.","DOI":"10.1007\/978-3-540-45198-3_26"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20211"},{"key":"ref30","unstructured":"N. Harms and Y. Yoshida, Downsampling for testing and learning in product distributions, in Proceedings of the International Colloquium on Automata, Languages and Programming, 2022, pp. 71:1\u201371:19."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/16M1065872"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3148"},{"key":"ref33","unstructured":"S. Raskhodnikova, Monotonicity Testing, Master\u2019s thesis, MIT, 1999."},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1145\/2382559.2382562"},{"key":"ref35","unstructured":"M. E. Saks and C. Seshadhri, Parallel monotonicity reconstruction, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2008."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M163339X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:14Z","timestamp":1787337794000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M163339X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,30]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/24M163339X"],"URL":"https:\/\/doi.org\/10.1137\/24m163339x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,30]]}}}