Approximating the Distance to Monotonicity of Boolean Functions

摘要

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," 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.