Premium
Simple analysis of graph tests for linearity and PCP
Author(s) -
Håstad Johan,
Wigderson Avi
Publication year - 2003
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10068
Subject(s) - linearity , simple (philosophy) , struct , mathematics , graph , function (biology) , simple graph , discrete mathematics , algorithm , computer science , physics , programming language , philosophy , epistemology , quantum mechanics , evolutionary biology , biology
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. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 139–160, 2003