Approximating the Distance to Monotonicity of Boolean Functions
Approximating the Distance to Monotonicity of Boolean Functions
复制标题
近似布尔函数的单调性距离
DOI：
10.1137/1.9781611975994.123
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Waingarten, Erik
中科院分区：
文献类型：
--
作者：
Pallavoor, Ramesh Krishnan;Raskhodnikova, Sofya;Waingarten, Erik
我们设计了一个非自适应算法，给定Oracle访问一个远离单调的函数，进行多查询并返回一个估计，该估计很有可能是对单调性的距离的近似。我们的算法的分析依赖于对Khot，Minzer和Safra（SIAM J. Comput.，2018年）。此外，我们排除了一个多查询非自适应算法，该算法可以更好地近似单调性的距离，因为对于所有常数，这个问题的每个非自适应近似算法都需要查询。这回答了Seshadhri（Property Testing Review，2014）关于非自适应算法的问题。我们通过证明擦除弹性（和容忍）测试器的类似界限来获得我们的下限。我们的方法也产生了相同的下界unjunta和a-junta。
We design a nonadaptive algorithm that, given oracle access to a function which is ‐far from monotone, makes poly queries and returns an estimate that, with high probability, is an ‐approximation to the distance of 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‐query nonadaptive algorithm that approximates the distance to monotonicity significantly better by showing that, for all constant every nonadaptive ‐approximation algorithm for this problem requires 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 ‐junta.