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.

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: