A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness

作者：Devadas Sheela^*; Rubinfeld Ronitt

来源：Theory of Computing Systems, 2016, 59(1): 99-111.

DOI：10.1007/s00224-015-9639-z

• Property testing
• Linearity testing

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.

• 出版日期2016-7
• 单位MIT