Approximating the Distance to Monotonicity of Boolean Functions We design a nonadaptive algorithm that, given a Boolean function fcolon 0,1n to 0,1 which is alphafar from monotone, makes poly(n, 1alpha) queries and returns an estimate that, with high probability, is an widetildeO(sqrtn)approximation to the distance of f to monotonicity. Furthermore, we show that for any constant kappa u003e 0, approximating the distance to monotonicity up to n12  kappafactor requires 2nkappa nonadaptive queries, thereby ruling out a poly(n, 1alpha)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 (nontolerant) testing of monotonicity that can be done nonadaptively with widetildeO(sqrtn  varepsilon2) queries.  :128,obtain our lower bound by proving an analogous bound for erasureresilient testers. An alphaerasureresilient 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 23) if the erasures can be filled in to ensure that the resulting function has the property and to reject (with probability at least 23) if every completion of erasures results in a function that is varepsilonfar from having the property. Our method yields the same lower bounds for unateness and being a kjunta. These lower bounds improve exponentially on the existing lower bounds for these properties.

Approximating the noise sensitivity of a monotone Boolean function The noise sensitivity of a Boolean function f: 0,1n rightarrow 0,1 is one of its fundamental properties. A function of a positive noise parameter delta, it is denoted as NS_deltaf. Here we study the algorithmic problem of approximating it for monotone f, such that NS_deltaf geq 1nC for constant C, and where delta satisfies 1n leq delta leq 12. For such f and delta, we give a randomized algorithm performing Oleft(fracmin(1,sqrtn delta log1.5 n) NS_deltaf textpolyleft(frac1epsilonright)right) queries and approximating NS_deltaf to within a multiplicative factor of (1pm epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omegaleft(fracmin(1,sqrtn delta)NS_deltaf cdot nxiright) on the query complexity of any algorithm that approximates NS_deltaf to within any constant factor, where xi can be any positive constant. Thus, our algorithmu0027s query complexity is close to optimal in terms of its dependence on n.  :145,introduce a novel descendingascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of thin functions with certain properties. The existence of such thin functions is proved using the probabilistic method. These techniques also yield previously unknown lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.