2023/04/03 by Black, Hadley, Chakrabarty, Deeparnab, Seshadhri, C.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2304.01416
Monotonicity testing of Boolean functions on the hypergrid, f:[n]d → \0,1\, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary n, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity \widetildeO(ε-4/3d5/6). This complexity is independent of n, but has a suboptimal dependence on d. Recently, [Braverman-Khot-Kindler-Minzer, ITCS 2023] and [Black-Chakrabarty-Seshadhri, STOC 2023] describe \widetildeO(ε-2 n3√(d)) and \widetildeO(ε-2 n√(d))-query testers, respectively. These testers have an almost optimal dependence on d, but a suboptimal polynomial dependence on n. In this paper, we describe a non-adaptive, one-sided monotonicity tester with query complexity O(ε-2 d1/2 + o(1)), independent of n. Up to the do(1)-factors, our result resolves the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of n yields a non-adaptive, one-sided O(ε-2 d1/2 + o(1))-query monotonicity tester for Boolean functions f:ℝd → \0,1\ associated with an arbitrary product measure.