%0 Journal Article
%T A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness
%A Sheela Devadas
%A Ronitt Rubinfeld
%J Computer Science
%D 2014
%I arXiv
%R 10.1007/s00224-015-9639-z
%X We present simple, self-contained proofs of correctness for algorithms for linearity testing and program checking of linear functions on finite subsets of integers represented as n-bit numbers. In addition we explore a generalization of self-testing to homomorphisms on a multidimensional vector space. We show that our self-testing algorithm for the univariate case can be directly generalized to vector space domains. The number of queries made by our algorithms is independent of domain size.
%U http://arxiv.org/abs/1412.5484v3