# Expanders, Property Testing and the PCP theorem

## Property Testing Lectures 1 and 2

Posted in lectures by atri on November 9, 2008

In the first two lectures on property testing, we started with codeword testing. A codeword tester for a code $C\subseteq \Sigma^m$, with query complexity $q$, is a randomized algorithm that given an input $\mathbf{y}\in\Sigma^m$ does the following:

1. If $\mathbf{y}\in C$, then the tester accepts with probability $1$,
2. If $\delta(\mathbf{y},C)\ge \epsilon$ then the tester rejects with probability $s>0$ (where $s$ can depend on $\epsilon$).
3. Makes at most $q$ oracle queries to $\mathbf{y}$.

We studied the Hadamard code $Had:\{0,1\}^n\rightarrow\{0,1\}^{2^n}$, where every codeword corresponds to the evaluation vector of a linear function $f:\{0,1\}^n\rightarrow\{0,1\}$ ($f$ being linear implies that for every $\mathbf{x},\mathbf{y}\in\{0,1\}^n$, $f(\mathbf{x})+f(\mathbf{y})=f(\mathbf{x}+\mathbf{y})$). This definition suggests a natural tester for the Hadamard code: think of the input from $\{0,1\}^{2^n}$as a function $g:\{0,1\}^n\rightarrow\{0,1\}$, pick random inputs $\mathbf{x},\mathbf{y}\in\{0,1\}^n$ and accept if and only if $g(\mathbf{x})+g(\mathbf{y})=g(\mathbf{x}+\mathbf{y})$. The tester makes only $3$ queries and obviously has perfect completeness. We saw an analysis using Fourier analysis in the lecture that showed that this tester rejects with probability at least $\delta(g,Had)$.

The “linearity tester” above was first analyzed in a paper titled Self-Testing/Correcting with Applications to Numerical Problems by Manuel Blum, Mike Luby and Ronitt Rubinfeld. The analysis of the soundess of the tester using Fourier analysis first appeared in the paper by Mihir Bellare, Don Coppersmith, Johan Hastad, Marcos Kiwi and Madhu Sudan titled Linearity Testing in Characteristic Two. I followed the presentation from these notes by Venkat Guruswami and Ryan O’Donnell.