Simple Analysis of Graph Tests for Linearity and PCP

Submitted by smcneil on Mon, 2012-01-16 00:00
Author: 
J. Hastad
A. Wigderson
Publication: 
Random Structures and Algorithms, vol. 22, no. 2, pp 139-160, 2003.
Conference on Computational Complexity, pp. 244-255, 2001. (see also ECCC)
Year: 
2003
Abstract: 
http://www.math.ias.edu/~avi/PUBLICATIONS/ABSTRACT/hw02.pdf
Files
File: 
Journal version (pdf)
Journal version (ps)