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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: