Isoperimetric inequalities for real-valued functions with applications to monotonicity testing

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions f:{0,1}d -> Double-struck capital R$$ f:{\left\{0,1\right\}}<^>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$$ f $$ over an arbitrary partially ordered domain as a collection of Boolean functions over the same domain, roughly capturing the distance of f$$ f $$ to monotonicity and the structure of violations of f$$ f $$ to monotonicity. We apply our generalized isoperimetric inequality to improve algorithms for testing monotonicity and approximating the distance to monotonicity for real-valued functions. Our tester for monotonicity has query complexity O similar to(min(rd,d))$$ \tilde{O}\left(\min \left(r\sqrt{d},d\right)\right) $$, where r$$ r $$ is the size of the image of the input function. (The best previously known tester makes O(d)$$ O(d) $$ queries, as shown by Chakrabarty and Seshadhri (STOC 2013).) Our tester is nonadaptive and has 1-sided error. We prove a matching lower bound for nonadaptive, 1-sided error testers for monotonicity. We also show that the distance to monotonicity of real-valued functions that are alpha$$ \alpha $$-far from monotone can be approximated nonadaptively within a factor of O(dlogd)$$ O\left(\sqrt{d\log d}\right) $$ with query complexity polynomial in 1/alpha$$ 1/\alpha $$ and the dimension d$$ d $$. This query complexity is nearly optimal for nonadaptive algorithms even for the special case of Boolean functions (The best previously known distance approximation algorithm for real-valued functions, by Fattal and Ron (TALG 2010) achieves O(dlogr)$$ O\left(d\log r\right) $$-approximation.).