## A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions
on $d$-Dimensional Hypergrids

by Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri

#### Oded's comments

Being preoccupied with other things,
I put aside looking at recent ECCC announcements.
I still cannot afford studying this work at depth,
but felt that I should put a recommendation for the result.

As is not stated in the paper,
this work focuses on a testing problem that was put forward
and initially studied in the
first paper on monotonicity testing.
In full generality, the aim is to test monotonicity
of function from $[n]^d$ to $[m]$,
whereas the current work considers the case of $m=2$.
Of course, subsequent works have greatly improved
over the aforementioned initial study,
where key improvements are the elimination of the dependence on $n$
(here)
and the celebrated KMS18 that provided
an almost optimal result for the case of $n=m=2$.

The current work aims at achieving the best of both worlds,
and succeeds in doing so.
Specifically, for $m=2$ and arbitrary $n$,
it describes a non-adaptive, one-sided tester
of query complexity $O(\epsilon^{-2} d^{1/2 + o(1)})$,
where $\epsilon $ denotes the proximity parameter.

#### The original abstract

Monotonicity testing of Boolean functions on the hypergrid,
$f:[n]^d \to \{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 $\widetilde{O}(\varepsilon^{-4/3}d^{5/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 $\widetilde{O}(\varepsilon^{-2} n^3\sqrt{d})$
and $\widetilde{O}(\varepsilon^{-2} n\sqrt{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(\varepsilon^{-2} d^{1/2 + o(1)})$,
independent of $n$. Up to the $d^{o(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(\varepsilon^{-2} d^{1/2 + o(1)})$-query monotonicity tester
for Boolean functions $f:\mathbb{R}^d \to \{0,1\}$
associated with an arbitrary product measure.

See ECCC TR23-048.

Back to
list of Oded's choices.