I am learning about Håstad 3-Query PCP theorem so what follows reflects my poor understanding of the subject.

I am slightly confused by the 3-queries that the verifier does to check if a given $\textsf{Label-Cover}$ instance, say $I = (G=(U \cup V, E), \Phi)$, is a Yes/No instance (satisfies $1-\epsilon$ of the constraints or at most $\epsilon$). Here $\Phi = \{ \phi_e: \Sigma \rightarrow \Sigma\colon e \in E\}$ is a collection of satisfying assignments for each edge and $[\Sigma]$ are the possible labels of $U$ and $V$.

I roughly understand the strategy. The verifier expects as a proof the labels of each vertex. This makes senses as we would like to check whether $\phi_{(u,v)}(l(u)) = l(v)$ meaning that the labels $l(u)$ of $u$ and $l(v)$ of $v$ form a satisfying assignment. One issue is that the proof $\pi$ is a binary string so the verifier assumes that the labels are encoded using long code.

Let $m = |\Sigma|$. The query procedure is then as follows:

  • Pick a random edge $(u, v) \in E$
  • Let $f_u, f_v$ be the long code of $u$ and $v$. Let $x,y \in \{-1, 1\}^m$ be random vectors and $\mu \in \{-1, 1\}^m$ be some noise vector.
  • Test: $f_u(x) f_v(y) = f((x \circ \phi_{(u,v)}) \mu y)$

Here is where I get confused. It seems that the verifier is able to select $f_u, f_v$, $x, y, \mu$. However, a PCP$[O(\log(n)), 3]$ verifier throws $O(\log(n))$ random coins which determine the 3 positions that will be queried. If I think of $f_u(x)$ as the outcome of a query, I don't understand how I can make my query correspond to the particular random choices of $(u, v),x, y, \mu$. Should I identify a random coin throw by the verifier as encoding a edge $(u, v)$, and vectors $x, y, \mu$?

Thanks in advance.

New contributor
User is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.