# Expanders, Property Testing and the PCP theorem

## Property Testing Lecture 4

Posted in lectures by atri on November 17, 2008

In the last lecture, we finished the proof of the soundness for the natural tester for testing graph bipartiteness. The main idea in the proof was to divide up the set of random vertices $S$ into two subsets $U$ and $W$. The analysis proceeded by showing that with high probability over the choices of $U$ and $W$, $W$ forms a “witness” to the fact that no bipartition of $U$ can be extended to a biparitiion of the input graph (which in turns implies that the input graph is not bipartite). The gain in this approach over the naive analysis is that $U$ has constant size and hence, one can take union bound over all possible partitions of $U$.

In the second part of the lecture, we studied Locally Decodable Codes (LDCs). In particular a $(q,\delta,\epsilon)$-locally decodable code $C\subseteq\Sigma^m$ has a local decoder with the following property. For any input $\mathbf{y}\in\Sigma^m$ (such that $\Delta(\mathbf{y},\mathbf{c})\le \delta m$ for a unique $\mathbf{c}\in C$) and $i\in [m]$, the decoder outputs the value $c_i$ with constant probability. We had already seen that the Hamming code is a $(2,\delta,1-2\delta)$-LDC for any $\delta<1/4$. Hamming code has the optimal block length for any 2-query LDC. We then saw a construction of a $(q,\delta,1-q\delta)$-LDC over $\mathbb{F}_r$ for $r\ge q+1$ based on Reed-Muller codes. The first chapter in Sergey Yekhanin‘s thesis has a nice introduction to these results.