首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties
  • 本地全文:下载
  • 作者:Deeparnab Chakrabarty ; Kashyap Dixit ; Madhav Jha
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the {\em uniform} distribution on the domain. This restriction to uniformity is more a matter of convenience than of necessity, and it is important to investigate distances induced by more general distributions.

    In this paper, we make significant strides in this direction. We give simple and optimal testers for {\em bounded derivative properties} over {\em arbitrary product distributions}. Bounded derivative properties include fundamental properties such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing

国家哲学社会科学文献中心版权所有