Simple analysis of graph tests for linearity and PCP
We give a simple analysis of the PCP with low amortized query complexity of Samorodnitsky and Trevisan [16]. The analysis also applies to the linearity testing over finite fields, giving a better estimate of the acceptance probability in terms of the distance of the tested function to the closest linear function. (C) 2003 Wiley Periodicals, Inc.
graph test pcp linearity testing iterated test pseudorandomness