文章基本信息

标题：Distribution-Free Testing of Linear Functions on â"â¿
本地全文：下载
作者：Noah Fleming ; Yuichi Yoshida
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：151
页码：1-19
DOI：10.4230/LIPIcs.ITCS.2020.22
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the problem of testing whether a function f:â"â¿ â' â" is linear (i.e., both additive and homogeneous) in the distribution-free property testing model, where the distance between functions is measured with respect to an unknown probability distribution over â"â¿. We show that, given query access to f, sampling access to the unknown distribution as well as the standard Gaussian, and Îµ > 0, we can distinguish additive functions from functions that are Îµ-far from additive functions with O((1/Îµ)log(1/Îµ)) queries, independent of n. Furthermore, under the assumption that f is a continuous function, the additivity tester can be extended to a distribution-free tester for linearity using the same number of queries. On the other hand, we show that if we are only allowed to get values of f on sampled points, then any distribution-free tester requires Î©(n) samples, even if the underlying distribution is the standard Gaussian.
关键词：Property Testing; Distribution-Free Testing; Linearity Testing