PCP

From ResearchWiki

What a PCP is:

A PCP for a problem in NP (3SAT, for example) will, given a proposed proof string π for an instance of that problem, return true or false. If π is correct, the PCP will always return true. If π is incorrect, the PCP will return true with probability . It does this by picking r bits at random. This string of r random bits is mapped to a set of q bits in π. Those q bits are passed through a verifier function that returns true or false with probabilities described above.

PCP's connection to hard approximations:

Under Construction

Walsh-Hadamard Code:

We define an operation as

mod 2

We define WH as follows. We let S be a list of all strings in {0,1}ⁿ in some canonical ordering. The i-th digit of WH(y) is .

An example, n = 3:
y = 101
000 101 = 0
001 101 = 1
010 101 = 0
011 101 = 1
100 101 = 1
101 101 = 0
110 101 = 1
111 101 = 0
Therefore WH(y) = 01011010
One important thing to note about the WH function is that any codeword W (such as 01011010) can be thought of as a linear function from where W(i) = W_i. Further,

where dist(a,b) is defined as the number of differing bits between a and b.

Because there are possible binary strings of length 2ⁿ, and only 2ⁿ Walsh-Hadamard codewords of length 2ⁿ, most strings of the correct length are invalid. We are therefore confronted with the challenge of, given a string in , determine if it is a valid WH codeword.