Publications
 • Isoperimetric Inequalities for RealValued Functions with Applications to Monotonicity Testing
 Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova
In submission.
 abstract
ECCC:TR20174
arXiv:1811.01427
We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of realvalued 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 realvalued function $f$ over an arbitrary partially ordered domain as a collection of Boolean functions over the same domain, roughly capturing the distance of $f$ to monotonicity and the structure of violations of $f$ to monotonicity.
We apply our generalized isoperimetric inequality to improve algorithms for testing monotonicity and approximating the distance to monotonicity for realvalued functions. Our tester for monotonicity has query complexity $\widetilde{O}(\min(r \sqrt{d},d))$, where $r$ is the size of the image of the input function. (The best previously known tester, by Chakrabarty and Seshadhri (STOC 2013), makes $O(d)$ queries.) Our tester is nonadaptive and has 1sided error. We show a matching lower bound for nonadaptive, 1sided error testers for monotonicity. We also show that the distance to monotonicity of realvalued functions that are $\alpha$far from monotone can be approximated nonadaptively within a factor of $O(\sqrt{d\log d})$ with query complexity polynomial in $1/\alpha$ and the dimension $d$. This query complexity is known to be nearly optimal for nonadaptive algorithms even for the special case of Boolean functions. (The best previously known distance approximation algorithm for realvalued functions, by Fattal and Ron (TALG 2010) achieves $O(d\log r)$approximation.)
 • Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in dDimensions
 Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2020.
 abstract
ECCC:TR18187
arXiv:1811.01427
We describe a $\tilde{O}(d^{5/6})$query monotonicity tester for Boolean functions $f:[n]^d \to \{0,1\}$ on the $n$hypergrid. This is the first $o(d)$ monotonicity tester with query complexity independent of $n$. Motivated by this independence of $n$, we initiate the study of monotonicity testing of measurable Boolean functions $f:\mathbb{R}^d \to \{0,1\}$ over the continuous domain, where the distance is measured with respect to a product distribution over $\mathbb{R}^d$. We give a $\tilde{O}(d^{5/6})$query monotonicity tester for such functions.
Our main technical result is a domain reduction theorem for monotonicity. For any function $f:[n]^d \to \{0,1\}$, let $\epsilon_f$ be its distance to monotonicity. Consider the restriction $\hat{f}$ of the function on a random $[k]^d$ subhypergrid of the original domain. We show that for $k = \text{poly}(d/\epsilon)$, the expected distance of the restriction is $\mathbb{E}[\epsilon_{\hat{f}}] = \Omega(\epsilon_f)$. Previously, such a result was only known for $d=1$ (BermanRaskhodnikovaYaroslavtsev, STOC 2014). Our result for testing Boolean functions over $[n]^d$ then follows by applying the $d^{5/6}\cdot \text{poly}(1/\epsilon,\log n, \log d)$query hypergrid tester of BlackChakrabartySeshadhri (SODA 2018).
To obtain the result for testing Boolean functions over $\mathbb{R}^d$, we use standard measure theoretic tools to reduce monotonicity testing of a measurable function $f$ to monotonicity testing of a discretized version of $f$ over a hypergrid domain $[N]^d$ for large, but finite, $N$ (that may depend on $f$). The independence of $N$ in the hypergrid tester is crucial to getting the final tester over $\mathbb{R}^d$.
 • A o(d) polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]^{d}
 Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2018.
 abstract
ECCC:TR17159
arXiv:1710.10545
We study monotonicity testing of Boolean functions over the hypergrid [n]^d and design a nonadaptive tester with 1sided error whose query complexity is O(d^{5/6}) \poly(\log n,1/\eps). Previous to our work, the best known testers had query complexity linear in d but independent of n. We improve upon these testers as long as n = 2^{d^{o(1)}}.
To obtain our results, we work with what we call "the augmented hypergrid", which adds extra edges to the hypergrid. Our main technical contribution is a Margulisstyle isoperimetric result for the augmented hypergrid, and our tester, like previous testers for the hypercube domain, performs directed random walks on this structure.
