Premium
Approximating the distance to monotonicity of Boolean functions
Author(s) -
Pallavoor Ramesh Krishnan S.,
Raskhodnikova Sofya,
Waingarten Erik
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21029
Subject(s) - monotonic function , property testing , mathematics , oracle , isoperimetric inequality , upper and lower bounds , monotone polygon , boolean function , function (biology) , discrete mathematics , combinatorics , triangle inequality , constant (computer programming) , algorithm , computer science , mathematical analysis , geometry , software engineering , evolutionary biology , biology , programming language
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 nonadaptiven 1 / 2 − κ‐approximation algorithm for this problem requires2n κ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.