首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Approximating the Distance to Monotonicity of Boolean Functions
  • 本地全文:下载
  • 作者:Ramesh Krishnan S. Pallavoor ; Sofya Raskhodnikova ; Erik Waingarten
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-24
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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.

  • 关键词:Erasure-Resilient Property Testing ; Monotonicity testing ; Tolerant testing
国家哲学社会科学文献中心版权所有