# PCP Theorem - Alphabet Reduction Step

What follows might seem stupid (and that probably reflects my poor understanding - so please bear with me)

I had a query on PCP theorem. We know that after the first three steps viz. Degree Reduction, Expanderization and Gap Amplification, we have a constraint graph $G$ with improved gap and huge alphabet size (like $\Sigma^{d^t}$). It is this problem that the alphabet reduction step addresses.

My question is that as outlined in Venkat Guruswami's lecture notes Introduction to Composition, it seems to me that the high level idea is to express the constraint $c_e$ over an edge $e$ as a Boolean constraint over boolean variables. This by itself achieves nothing and we also need to apply the PCP reduction ,$P_e$, on this edge. This "looks like" a recursive invocation of PCP and this is where I start getting a little worried. It seems as this recursive invocation would blow up the alphabet size again.

The authors have offered some explanation by observing that this recursion has a "base case" - namely - the "inner" PCP reduction applies only to constraints of constant size.

(By this I understand that the inner recursion gets invoked only when we are looking at constraints $c_e$ over a single edge which is a binary constraint, but still I have not yet come over the fear that somehow we still might blow up the alphabet size instead of shrinking it). To me, it still seems that a recursive repetition of Gap Amplification step will only make matters worse by blowing up the alphabet size unless we incorporate measures to handle the base case a little differently.

I hope my query (as silly as it is) is probably clear. Please let me know what essential part am I missing (or have misunderstood).

• Just read the notes of the next lecture. (P.S. You actually mean, you have a question about Dinur's proof of the PCP theorem) Nov 26, 2010 at 11:59