3
$\begingroup$

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.
$\endgroup$

0

Your Answer

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