A \({d}^{{1/2+{o}(1)}}\) Monotonicity Tester for Boolean Functions on \({d}\)-Dimensional Hypergrids
Hadley Black, Deeparnab Chakrabarty, Comandur Seshadhri · SIAM Journal on Computing · 2025
Abstract. 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–1994] describes 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–25:24] and H. Black, D. Chakrabarty, and C. Seshadhri [ Proceedings of the 55 th Annual ACM Symposium on Theory of Computing, 2023, pp. 233–241] 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.