All reports by Author Deeparnab Chakrabarty:

__
TR23-048
| 4th April 2023
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids

__
TR22-162
| 10th November 2022
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\widetilde{O}(n\sqrt{d})$ Monotonicity Tester

__
TR18-187
| 4th November 2018
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids

Revisions: 4

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

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 ... more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

The problem of testing monotonicity for Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$ is a classic topic in property testing. When $n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making $\widetilde{O}(\varepsilon^{-2}\sqrt{d})$ queries. Up to polylog ... more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Testing monotonicity of Boolean functions over the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic problem in property testing. When the range is real-valued, there are $\Theta(d\log n)$-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:

(1) Independence of $n$: There are testers ...
more >>>