Approximating the Distance to Monotonicity of Boolean Functions
share
We design a nonadaptive algorithm that, given a Boolean function f{0,1}^n →{0,1} which is α-far from monotone, makes poly(n, 1/α) queries and returns an estimate that, with high probability, is an O(√(n))-approximation to the distance of f to monotonicity. Furthermore, we show that for any constant κ > 0, approximating the distance to monotonicity up to n^1/2 - κ-factor requires 2^n^κ nonadaptive queries, thereby ruling out a poly(n, 1/α)-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 O(√(n) / ε^2) queries. We obtain our lower bound by proving an analogous bound for erasure-resilient testers. An α-erasure-resilient tester for a desired property gets oracle access to a function that has at most an α 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 ε-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.
READ FULL TEXT