ECCC-Report TR19-163https://eccc.weizmann.ac.il/report/2019/163Comments and Revisions published for TR19-163en-usThu, 25 Feb 2021 08:03:45 +0200
Revision 1
| Approximating the Distance to Monotonicity of Boolean Functions |
Ramesh Krishnan S. Pallavoor,
Sofya Raskhodnikova,
Erik Waingarten
https://eccc.weizmann.ac.il/report/2019/163#revision1We design a nonadaptive algorithm that, given oracle access to a function $f: \{0,1\}^n \to \{0,1\}$ which is $\alpha$-far from monotone, makes poly$(n, 1/\alpha)$ queries and returns an estimate that, with high probability, is an $\widetilde{O}(\sqrt{n})$-approximation to the distance of $f$ to monotonicity. The analysis of our algorithm relies on an improvement to the directed isoperimetric inequality of Khot, Minzer, and Safra (SIAM J. Comput., 2018). Furthermore, we rule out a poly$(n, 1/\alpha)$-query nonadaptive algorithm that approximates the distance to monotonicity significantly better by showing that, for all constant $\kappa > 0,$ every nonadaptive $n^{1/2 - \kappa}$-approximation algorithm for this problem requires $2^{n^\kappa}$ queries. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. We obtain our lower bound by proving an analogous bound for erasure-resilient (and tolerant) testers. Our method also yields the same lower bounds for unateness and being a $k$-junta.Thu, 25 Feb 2021 08:03:45 +0200https://eccc.weizmann.ac.il/report/2019/163#revision1
Paper TR19-163
| Approximating the Distance to Monotonicity of Boolean Functions |
Ramesh Krishnan S. Pallavoor,
Sofya Raskhodnikova,
Erik Waingarten
https://eccc.weizmann.ac.il/report/2019/163We design a nonadaptive algorithm that, given a Boolean function $f\colon \{0,1\}^n \to \{0,1\}$ which is $\alpha$-far from monotone, makes poly$(n, 1/\alpha)$ queries and returns an estimate that, with high probability, is an $\widetilde{O}(\sqrt{n})$-approximation to the distance of $f$ to monotonicity. Furthermore, we show that for any constant $\kappa > 0,$ approximating the distance to monotonicity up to $n^{1/2 - \kappa}$-factor requires $2^{n^\kappa}$ nonadaptive queries, thereby ruling out a poly$(n, 1/\alpha)$-query nonadaptive algorithm for such approximations. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. Approximating the distance to a property is closely related to tolerantly testing that property. Our lower bound stands in contrast to standard (non-tolerant) testing of monotonicity that can be done nonadaptively with $\widetilde{O}(\sqrt{n} / \varepsilon^2)$ queries.
We obtain our lower bound by proving an analogous bound for erasure-resilient testers. An $\alpha$-erasure-resilient tester for a desired property gets oracle access to a function that has at most an $\alpha$ fraction of values erased. The tester has to accept (with probability at least 2/3) if the erasures can be filled in to ensure that the resulting function has the property and to reject (with probability at least 2/3) if every completion of erasures results in a function that is $\varepsilon$-far from having the property. Our method yields the same lower bounds for unateness and being a $k$-junta. These lower bounds improve exponentially on the existing lower bounds for these properties.Sat, 16 Nov 2019 18:11:38 +0200https://eccc.weizmann.ac.il/report/2019/163