Simple Analysis of Graph Tests for Linearity and PCP
| Author(s) : | Avi Wigderson, |
| Publisher : | N/A |
| Publication Date : | 2001 |
| ISSN : | N/A |
| Abstract : | 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 nite elds, giving a better estimate of the acceptance probability in terms of the distance of the tested function to the closest linear function., |