# What does Håstad verifier query?

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$$?