The standard definition of property testing endows the tester with the ability to make arbitrary queries to ``elements''of the tested object.In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object.While sample-based testers were defined byGoldreich, Goldwasser, and Ron ({em JACM}/ 1998), most research in property testing is focused on query-based testers.In this work, we advance the study of sample-based property testers by providing several general positive results as well as by revealing relations between variants of this testing model. In particular:We show that certain types of query-based testers yield sample-based testers of sublinear sample complexity.For example, this holds for a natural class of proximity oblivious testers.We study the relation between distribution-free sample-based testers and one-sided error sample-based testers w.r.t the uniform distribution.While most of this work ignores the time complexity of testing, one part of it does focus on this aspect. The main result in thispart is a sublinear-time sample-based tester for k-Colorability, for any k2.
展开▼
机译：属性测试的标准定义使测试人员能够对被测试对象的``元素''进行任意查询，相比之下，基于样本的测试人员只能获取被测试对象的独立分布的元素（也称为带标签的样本）。基于样本的测试人员由Goldreich，Goldwasser和Ron（{ em JACM} // 1998）定义，大多数属性测试的研究都集中于基于查询的测试人员。在这项工作中，我们推进了基于样本的属性测试人员的研究。通过提供一些总体正面结果以及揭示此测试模型的变体之间的关系。特别是：我们证明了某些类型的基于查询的测试员会产生基于子线性样本复杂度的基于测试员的测试员，例如，这适用于自然类的邻近遗忘测试员。我们研究了无分布基于样本的测试员与基于单边错误样本的测试器具有均匀的分布。尽管大部分工作都忽略了测试的时间复杂性，但其中一部分的确着眼于这一方面。本部分的主要结果是针对任何k2的亚线性时间基于样本的k-色性测试仪。
展开▼
