Simple analysis of graph tests for linearity and PCP
2003 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 22, no 2, 139-160 p.Article in journal (Refereed) Published
We give a simple analysis of the PCP with low amortized query complexity of Samorodnitsky and Trevisan . 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.
Place, publisher, year, edition, pages
2003. Vol. 22, no 2, 139-160 p.
linearity testing, PCP, graph test, iterated test, pseudorandomness, hardness, proofs
IdentifiersURN: urn:nbn:se:kth:diva-22270DOI: 10.1002/rsa.10068ISI: 000181119600001OAI: oai:DiVA.org:kth-22270DiVA: diva2:340968
QC 201005252010-08-102010-08-10Bibliographically approved