  We study the problem of testing whether a function f:R^n->R 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 R. We show that, given query access to f,
sampling access to the unknown distribution as well as the standard Gaussian,
and eps>0, we can distinguish additive functions from functions that are
eps-far from additive functions with O((1/eps)log(1/eps)) 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 Omega(n) samples, even if the underlying distribution is the
standard Gaussian.
