Approximating the distance to monotonicity of Boolean functions. Issue 2 (24th June 2021)

• Record Type: Journal Article
• Authors: Pallavoor, Ramesh Krishnan S.; Raskhodnikova, Sofya; Waingarten, Erik
• Is Part Of: Random structures & algorithms. Volume 60:Issue 2(2022)
• Page Start: 233
• Page End: 260
• Publication Date: 2021-06-24
• Subjects: analysis of Boolean functions -- property testing -- sublinear algorithms -- tolerant and erasure‐resilient testing; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21029
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We design a nonadaptive algorithm that, given oracle access to a 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 Õ ( 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 / α ) ‐query nonadaptive algorithm that approximates the distance to monotonicity significantly better by showing that, for all constant κ > 0, every nonadaptive n 1 / 2 − κ ‐approximation algorithm for this problem requires 2 n κ 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.