All reports by Author Hadley Black:

__
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

__
TR20-174
| 18th November 2020
__

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova#### Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

__
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

__
TR17-159
| 28th October 2017
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### A $o(d) \cdot \text{polylog}~n$ Monotonicity Tester for Boolean Functions over the Hypergrid $[n]^d$

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, Iden Kalemaj, Sofya Raskhodnikova

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions $f \colon \{0,1\}^d\to\mathbb{R}$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function $f$ over an arbitrary partially ... 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 >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

We study monotonicity testing of Boolean functions over the hypergrid $[n]^d$ and design a non-adaptive tester with $1$-sided error whose query complexity is $\tilde{O}(d^{5/6})\cdot \text{poly}(\log n,1/\epsilon)$. Previous to our work, the best known testers had query complexity linear in $d$ but independent of $n$. We improve upon these testers as ... more >>>