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

Sheela Devadas, Ronitt Rubinfeld

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…