This post gives a gentle introduction to the Probabilistic Checkable Proof (PCP), the pearl of computational complexity theory.

Introduction

Consider the canonical NP problem, boolean satisfiability (SAT). To determine if a Boolean formula is satisfiable, a deterministic verifier needs to check a polynomial length proof — the assignment of each variable. But what if the verifier is allowed to use randomness and to fail with a small probability? It turns out that the probablistic verifier still needs a polynomial-size proof, but it does not need to look at all of it. With oracle access to the proof, it only needs to make constant queries to the proof, i.e. check constant number of locations of the proof. The proof string is of course much more complex than the assignment of each variable. We call these proofs “probablistic checkable proofs” (PCP). The aforementioned fact about NP is the famouse PCP theorem, and in this post, we will walk through the key components of the proof.

Definition

A Language $L$ is in the complexity class PCP$_{c, s}[r, q]_\Sigma$ if there exists a polynomial-time probablistic oracle Turing machine called the PCP verifier $V_L$ such that

• $\Sigma$ is the alphabet for the proofs
• $V_L$ uses $r$ bits of randomness and $q$ queries
• Completeness: If $x \in L$, there exists a proof $\pi$ such that $\Pr_{\rho \sim \{0,1\}^q}[V_L^\pi(x; \rho) = 1] \geq c$ for some $0<c\leq1$
• Soundness: If $x \notin L$, for all proofs $\pi$, $\Pr_{\rho \sim \{0,1\}^q}[V_L^\pi(x; \rho) = 1] \leq s$ for some $0\geq s<1$

Basic Examples and Results

• PCP$_{c, s}[0, 0]_\Sigma$ = P
• PCP$_{1, 0}[O(\log(n)), 0]_\Sigma$ = P
• PCP$_{c, s}[poly(n), 0]_\Sigma$ = BPP
• PCP$_{c, s}[0, poly(n)]_\Sigma$ = NP
• PCP$_{1, 0}[O(\log(n)), poly(n)]_\Sigma$ = NP

Usually $\Sigma = \{0,1\}$ and we simply drop $\Sigma$. Further, if we drop the completeness and soundness parameters, we implicity assume that $c=1, s=\frac{1}{2}$. Note that given $r$ bits of randomness and $q$ queries, the verifier can check at most $2^r q$ locations of the proof, which is the effective size of any proof. (Here, we assume the verifier is non-adaptive.)

The Statement of the PCP Theorem

The theorem demands a very intricate proof, which is of polynomial size and requires only constant number of queries. The proof we will explore is based on “proof composition”. We will construct two not so strong proofs: a very long proof (exponential-size) that requires only constant number of queries, and a short proof (polynomial size) that requires polylog queries. Then we will compose them to take the merits of both. Thus, the outline of the proof will contain three main components: (1) an exponential-size PCP, (2) a polynomial-size PCP, and (3) the proof composition. Generally speaking, every PCP is a smart coding of the plain proof, so we will use different codes borrowed from coding theory throughout the journey.

Exponential-size PCP

Note that the effective proof size is $2^{poly(n)} \cdot O(1) = \exp(poly(n))$, hence the name exponential-size PCP. To prove this statement, we will consider a NP-complete problem called QUADEQ, which determines if a system of quadratic equations has a satisfying assignment. The prover should use Walsh-Hadamard code to construct a exponential-size PCP of the satisfying assignment. The verifier will first use linearity testing to verify the validity of the codeword, i.e., to check that the proof is indeed the Walsh-Hadamard code of some string. Then it can use constant queries to verify if the string is a satisfying assignment with high probability.

QUADEQ

A quadratic equation of $n$ variables $u_1, \dots, u_n$ over $GF(2)$ has the form $\sum_{i, j \in [n]} a_{i,j} u_iu_j = b$. A system of quadratic equations over $GF(2)$ is in QUADEQ if the system has a satisfying assignment $u \in \{0, 1\}^n$.

The polynomial-size proof of QUADEQ is simply the satisfying assignment of the variables $u$, so QUADEQ is clearly in NP. To see that QUADEQ is NP-complete, it is easist to reduce from circuit-satisfiabily. We can assign a variable to represent the output of each gate in the circuit:

• $u_k = u_i \land u_j \quad \to \quad u_k = u_iu_j$
• $u_k = u_i \lor u_j \quad \to \quad u_k = u_i + u_j + u_i u_j$
• $u_k = \lnot u_i \quad \to \quad u_k = 1 - u_i$.

This conversion of a problem instance to a set of equations is known as arithmetization.

Walsh-Hadamard Code

To construct a exponential-size PCP, we will make use of the Walsh-Hadamard code. Given a message $u \in \{0,1\}^n$, its Walsh-Hadamard codeword is $H(u) \in \{0,1\}^{2^n}$, where $H(u)(x) = u \odot x$. Here $x \in \{0,1\}^n$ is the index of $H(u)$, a string of exponential size, and $u \odot x$ is the dot-product of $u$ and $x$.

Random Subsum Principle

As a fundamental principle of coding, if the messages $u$ and $v$ differs in a few locations, we want their codewords to differ in almost all the locations. This is indeed true to Walsh-Hadamard Code, which can be summarized as the random subsum principle:

Linear Functions

Another principle of coding is that the verifier should be able to check the validity of a codeword, i.e., the given string is the codeword of some string, or the given string is close to the codeword of some string. To demonstrate this property, we will consider the Walsh-Hadamard codeword of $u$ as a linear function $l_u: \{0,1\}^n \to \{0,1\}$ defined by $l_u(x) = H(u)(x) = u \odot x$. In general, a linear function $f: \{0,1\}^n \to \{0,1\}$ satisfies $f(u+v) = f(u)+f(v)$. It’s straightforward to see that $l_u$ is indeed a linear function. Conversely, every linear function $f$ can be written as $f=l_u$ for some $u \in \{0,1\}^n$. Let $e_i \in \{0,1\}^n$ be the string with a single $1$ at the $i$-th location. Then $u_i = f(e_i)$. Thus, the Walsh-Hadamard code is equivalent to linear functions over $GF(2)$. To check the validity of a codeword is to test whether it is close to a linear function.

BLR Linearity Testing

Formally, we say that a function $f$ is $\rho$-close to a linear function $l_u$ if

The BLR linearity testing is actually very simple: we randomly query two locations $x$ and $y$, and test if $f(x)+f(y) = f(x+y)$. Nevertheless, it is very powerful. We state without a proof of the following theorem: If

$f$ is $\rho$-close to some linear function.

This suggests a simple probabilistic algorithm for linearity testing, and hence verifying a Walsh-Hadamard code.

Local Decoding

Walsh-Hadamard code is also a locallly decodable code, i.e., we can recover a single bit of a corrupted codeword while making constant number of queries. Suppose $f$ is $(1-\delta)$-close to a linear function $g$ (a Walsh-Hadamard codeword), and we want to decode $g(x)$, but $f(x)$ is corrupted. Then we can pick a random $r \in \{0,1\}^n$, and since

we can decode $g(x)$ by querying $f(x+r)$ and $f(r)$ if these two locations are not corrupted. If the codeword is corrupted at every location with the same probability, then this procedure actually makes things worse. However, in our PCP system in the later sections, we only want to check for specific locations of the codeword. In this case, the local decoding procedure guards against a malicious prover who will concentrate the corruptions on the certain locations we are looking at.

An Exponential-size PCP for QUADEQ

QUADEQ asks, given $m$ quadratic equations of $n$ variables, if there is satisfying assignment of the variables. Equivalently, QUADEQ asks, given inputs $A$ and $b$, where $A$ is a $m \times n^2$ matrix, and $b$ is an $m$ dimensional vector, if there is a $n^2$ dimensional vector $U$ such that $U = u \otimes u$ and $AU = b$. Here $u$ should be a satisfying assignment.

Our exponential-size PCP should be $f = WH(u)$ and $g = WH(U)$, where $U = u \otimes u$. Now the verifier will carry out the following steps:

• (Linearity Test) Check that $f$, $g$ are linear functions, i.e., $f$, $g$ are Walsh-Hadamard code- words.
• (Tensor Test) Check that $f$, $g$ encode the same source word, i.e., $g$ encodes $u \times u$ and f encodes $u$.
• (Satisfiability Test) Check that $AU = b$.

We’ve already discussed the linearity test. We will describe the remaining two steps.

Tensor Test

The idea of tensor test is very straightforward. If $f = WH(u)$ and $g = WH(u \otimes u)$ for some $u$, then

Thus, given two linear functions $f: \{0,1\}^n \to \{0,1\}$ and $g: \{0,1\}^{n^2} \to \{0,1\}$, the tensor test is as following:

• Choose $r,r' \in \{0,1\}^n$ uniformly at random.
• Accept if $g(r \otimes r') = f(r)f(r')$

The protocol is clearly complete. It is also sound: if g and r linear functions, based on random subsum principle, it can be shown that each tensor test rejects correctly with at least $\frac{1}{4}$ probability. Thus, it is also efficient: we only need to repeat the test constant number of times to achieve desired parameters. The final caveat is that from linearity testing, we only have the gurantee that $g$ and $f$ are close to linear functions. This is a problem since we are only checking specific locations of $g$, to be exact, $1/n$ fraction of locations. This is why local decoding we’ve discussed above is necessary to achieve soundness constraints.

Satisfiability Test

The satisfiability test is also quite straightforward:

• Choose $r \in \{0,1\}^m$ uniformly at random.
• Accept if $r \odot (AU) = g(A^Tr) = r \odot b$

Again, based on the random subsum principle, each test rejects correctly with at least $\frac{1}{2}$ probability. Again, we only need to repeat the test constant number of times to achieve desired parameters.

Summary of Exponential-size PCP

As a recap, the exponential-size PCP verifier uses four testing procedures: linearity test, tensor test (with local decoding), and satisfiability test. Each procedure achieves constant soundness with constant number of queries, and thus we can repeat each procedure constant number of times to achieve overall constant soundness with constant number of queries.

Polynomial-size PCP

Here, the effective proof size is $2^{O(\log(n))} \cdot \log^{O(1)} n = poly(n)$, hence the name polinomial-size PCP. To prove this statement, we will again consider the NP-complete problem QUADEQ. But instead of quadratic equations over $\mathbb F_2$, we will consider the general problem of quadratic equations over an arbitrary finite field $\mathbb F$, which is still a NP-complete problem. For the exponential-size PCP, the proof is some version of the satisfying assignment encoded by the Walsh-Hadamard code, which corresponds to linear functions. For the polynomial-size PCPs, we will also use techniques from coding theory, namely low-degree extension and Reed-Muller code, which are closely related and correspond to low-degree polynomial functions. Reed-Muller code won’t be used explicity in the proof, but will be used to encode or amplify the problem instance so that the verifier can check satisfiability with small number of random bits. Then, the main proof will be the low-degree extension of the satisfying assignment, and with the clever SumCheck protocol, the verifier can check the assignment with small number of queries. Additionally, like linearity testing for the exponential-size PCP, the verifier will need to verify the validity of the proof with low-degree testing first.

Amplifying the QUADED with Reed-Muller code

Let’s remind of ourselves the QUADEQ problem: we are given $m$ quadratic equations of $n$ variables: $p_1, \dots, p_m \in \mathbb F[x_1, \dots, x_n]$, and we want to know if there is a common zero of the equations $\mathbf x \in \mathbb F^n$. For the exponential-size PCP, we have to use $poly(n)$ number of random bits, essentially because we check the satisfiability of each equation. We will try to tackle this first.

First Naive Solution

What if we just pick an equation at random? This only uses $\log(m)$ number of bits, which is on the order of $\log(n)$. The number of queries depend on the arity of the equation we selected, which could be potentially $n$, which would be a problem. However, from the reduction of the circuit satisfiability problem, we can restrict the problem to quadratic equations of max arity $\leq 3$, while still resulting in a NP-complete problem. So we actually only need constant number of queries.

However, the soundness is fairly bad. In the worst case, there is an assignment $\mathbf x$ that satisfies $m-1$ equations, then our soundness is only $1/m$. Remember that we need constant soundness so that we can easily amplify it without blowing up the number of random bits or queries.

Reed-Solomon code

To resolve the problem, we need to leverage coding theory to “spread the error”. Roughly, we want to construct more equations so that if an original equation is not satisfied, a lot of constructed equations will not be satisfied.

To achieve this, consider a non-zero message of length $m$, $\mathbf u = (u_1, \dots, u_m) \in \mathbb F^m$. The encoding is a code of length $l$, which corresponds to the evaluations of a polynomial $p$ at $l$ arbitrary different locations, say $x_1, \dots, x_l \in \mathbb F$. The polynomial $p$ is defined by

i.e., the coefficients of the polynomial is defined by the message. Then the code is $\mathbf v = (f(x_1), \dots, f(x_l))$. Since $p$ is a degree $m-1$ polynomial, it has at most $m-1$ roots. And thus if $\mathbf u \neq \mathbf 0$, there are at most $m-1$ zero coordinates in $\mathbf v$; then, if we pick a random coordinate of $\mathbf v$, we have a $\frac{l-m+1}{l}$ probability to find a non-zero coordinate, which can be made constant if we take say $l = 2m$.

This encoding procedure is a linear transformation via the Vandermonde matrix $T \in \mathbb F^{l\times m}$:

such that $\mathbf v = T u$.

If we consider our $m$ quadratic functions as a vector function $\mathbf p = (p_1, \dots, p_m)$, we can similarly encode the vector function to get a new vector function $\mathbf q = T \mathbf p$. Or equivalently, for every evaluation of our quadratic equations, we encode the result with $T$. Then if $\mathbf p(\mathbf x)$ where $\mathbf x \in \mathbb F^n$ has one non-zero coordinate, at least $\frac{l-m+1}{l}$ cooridinates of $\mathbf q(\mathbf x)$ are non-zero.

In this way, we achieve constant soundness and we don’t need much randomness. We only need to use $\log l$ number of random bits, which is still on the order of $m$. However, we have a problem with the number of queries. Namely, to have $l$ different locations in $\mathbb F$, $|\mathbb F| \geq l$. But as we will see, we need the size of $\mathbb F$ to be smaller to achieve small number of queries.

Reed-Muller code

To reduce the size of $\mathbb F$, we need to use Reed-Muller code, which extends from single-variable polynomials to multi-variable polynomials. Given a message of length $m$, $\mathbf u = (u_1, \dots, u_m) \in \mathbb F^m$, we will use the message as the coefficients of a multi-variable polynomial $f$. We assume that

for some integer $r$ representing the degree of $f$ and integer $k$ representing the number of variables. Then we can define

where $u_S$ indexes $u$. With Reed-Muller code, we can choose $r$ and $k$ properly to ensure that $|\mathbb F| = polylog(m)$. Further, we will have $|\mathbb F^k| = poly(m)$ new polynomial equations, and we will achieve constant soundness by randomly picking one equation.

Low-Degree Extension

Now with Reed-Muller code to encode the equations, we are left to deal with $poly(m)$ equations and we can randomly check one of them to achieve constant soundness. However, we have a big problem with the query complexity. Namely, both the Reed-Solomon and Reed-Muller code “spread” the variables into new polynomials, so that each new polynomial now may have max arity of $n$. This will require us to query all positions of the assignment provided by thr prover, but we want to achieve query complexity of $polylog(n)$.

To circumvent checking all coordinates, we will require the prover to provide instead an encoding of the satisfying assignment, the low-degree extension of the assignment. Given an assignment $a: [n] \to \mathbb F$, we will consider a subfield $\mathbb H \subset \mathbb F$ and an integer $l$, such that $|\mathbb H|^l = n$. Then, we can view the assignment function as $a: \mathbb H^l \to \mathbb F$. In effect, we are using $l$ coordinates over a small field to index $n$ coordinates.

Finally, we will claim without a proof (which is not complicated) that we can always construct a low-degree extension $\hat a: \mathbb F^l \to \mathbb F$ such that $\hat a|_{\mathbb H^l} = a$ and individual degree of $\hat a < |\mathbb H|$. We will ask the prover to send the evaluation table of this low-degree extension $\hat a$ as a part of the proof to the verifier.

Why will this help at all? Let’s consider more concretly the task of the verifier. Suppose that the verifier uses Reed-Muller code and randomly pick a new polynomial

where we drop the degree $1$ terms and constants for simplicity of discussion, and split the coefficients for symmetric terms like $x_1x_2, x_2x_1$. Let’s now use the indexing with $l$ coordinates from $\mathbb H$ instead and apply the low-degree extension of assignment $\hat a$:

Note that $c_st$ is computed by the verifier and can be viewed as a function $c: \mathbb H^{2l} \to \mathbb F$. The verifier can find the low-degree extension of it $\hat c: \mathbb F^{2l} \to \mathbb F$. Let’s view the summand as a single function

so that the evaluation of $q$ becomes

Why will this transformation be helpful? We will soon discuss the SumCheck protocol, which can cleverly evaluate the equation with the prover. Instead of substituting in all $|\mathbb H|^{2l}$ terms, the protocol checks each of the $2l$ coordinates one by one, resulting in query complexity on the order of $O(l|\mathbb H|)$. Note that the individual degree of $g(\mathbf u)$ is bounded by $2|\mathbb H|$, which is criticial for this protocol.

SumCheck Protocol

Let’s consider more generally the SumCheck protocol, and analyze its application to our particular problem in the end. We will first introduce the SumCheck Protocol as an IP (interactive proof) protocol, for which the prover and verifier communicates back and forth.

The problem considers a polynomial function $f: \mathbb F^n \to \mathbb F$, where $f$ has a small individual degree $d < |\mathbb F|$ in every variable. The verifier wants to check the value of

where $\mathbb H \subset \mathbb F$ is a subfield.

Besides our problem, a very useful scenario is when $f$ encodes a Boolean formula, $\mathbb H = \mathbb F_2$, and $\mathbb F = \mathbb F_p$ for some large prime $p > 2^n$. In this case, $d$ is on the order of clauses, and the problem is asking for the number of satisfying assignments to $f$. Thus, with the SumCheck Protocol, we can prove many results related to the complexity class IP.

The verifier will pick $n$ random elements $r_1, \dots, r_n \in \mathbb F$, and define the following functions:

We can make the following observations:

Note that $f_0$ is the solution we’re looking for, $f_n(r_n)$ is easily computable, and the recursive relation motivates a recursive IP protocol as follows:

1. The verifier receives $\hat{f_0} \in \mathbb F$ from the prover.
2. The verifier receives a polynomial $\hat{f_1}$ of degree $\leq d$ (the coefficients) from the prover, and checks that $\sum_{x \in \mathbb H}f_1(x) = f_0$.
3. For $i=2\cdots n$, the verifier sends $r_{i-1}$ to the prover, and the prover sends back a polynomial $\hat f_i$, and the verifier checks that $\sum_{x \in \mathbb H}f_i(x) = f_{i-1}(r_{i-1})$.
4. Finally, the verifier checks that $\hat f_n(r_n) = f_n(r_n)$.

Now the protocol is clearly complete: the prover just needs to send the information as defined. The number of random bits we need is $n |\mathbb F|$. Now the interesting part is the completeness, which calls into attention the requirement that $d$, the individual degree of $f$, is small (compared to $|\mathbb F|$). Assume that the verifier accepts at the last step. If $\hat f_n(r_n) \neq f_n(r_n)$, the function $\hat g(x) = \hat f_n(x) - f_n(r_n)$ is a polynomial of maximal degree $d$ (we can directly reject if the prover sends a higher order polynomial). Thus, $r_n$ is a root of $f(x)$ with probability $\leq d / |\mathbb F|$. Then we can make inductive steps, assuming that $\hat f_i = f_i$, by the same logic, $\hat f_{i-1} \neq f_{i-1}$ with probability $\leq d / |\mathbb F|$. Finally, by the union bound, we falsely accept with probability $\leq nd / |\mathbb F|$.

Now in the context of PCPs, the prover has to send a single (poly-size) proof instead of interactively communicating. Thus, the prover needs to write down the proof in respect to every possible trace of randomness. In effect, this is a tree of depth $n$, where each parent has $|\mathbb F|$ children. And for each child, the prover needs to write down the coefficients of the polynomial of degree $\leq d$, so the total length is $O(d|\mathbb F|^n)$. Finally, for each round, the verifier needs to query a polynomial of degree $\leq d$, so the total queries is $O(dn)$.

Now back to the context of our problem. We have that $d = 2|\mathbb H|, n = 2l$. We will need to define the parameters for our low-degree extension as follows:

Thus, for the SumCheck protocol, we will achieve soundness of $O(\delta)$, proof length of $O(|\mathbb H||\mathbb F|^l) = poly(n)$, number of queries equal to $O(l|\mathbb H|) = polylog(n)$, and randomness of $O(l|\mathbb F|) = O(\log n)$.

Finally, note that we cannot arbitrarily decide $|\mathbb F|$. This is constrained by the code we used to amplify the equations. Recall that Reed-Solomon code will require $|\mathbb F| = poly(n)$, thus not applicable in our scenario. Luckily, Reed-Muller code suffices for our case.

Low-degree Testing

A final step to complete the proof is a low-degree testing. We ask for a low-degree extension of the assignment function from the prover, and we need to make sure that’s the case. We will skip the detailed algorithm and proof for this testing, but provide the following fact which motivates the algorithm.

Given a multivariate function $f \in \mathbb F^{\leq d}[x_1, \dots, x_n]$, for $\mathbf x, \mathbf h \in \mathbb F_p^n$, where $p$ is a prime,

where

The test basically involves randomly sampling $\mathbf x, \mathbf h \in \mathbb F_p^n$ and tests for this local property.

PCP Theorem via Proof Composition

Now we’ve introduced two weaker PCP theorems, we will sketch how to compose them to prove the PCP theorem. In order to do that, we introduce two variants of PCPs, whose purposes will be explicit once we get to proof composition.

PCP of Proximity (PCPP)

We now present a relaxation of PCPs that only verify that the input is close to an element of the language. The advantage of this relaxation is that it allows the possibility that the verifier may read only a small number of bits from the input. Actually, for greater generality, we will divide the input into two parts $(x,y)$, giving the verifier $x$ explicitly and $y$ as an oracle, and we only count the verifier’s queries to the latter. Thus we consider languages consisting of pairs of strings. For a pair language $L$, we define $L(x) = \{y: (x,y) \in L\}$.

Definition

A Language $L$ is in the complexity class PCPP$_{c, s, \delta}[r, q]_\Sigma$ if there exists a polynomial-time probablistic oracle Turing machine called the PCPP verifier $V_L$ such that

• Completeness: If $x \in L$, there exists a proof $y \circ \pi$ such that $\Pr_{\rho \sim \{0,1\}^q}[V_L^{y \circ \pi}(x; \rho) = 1] > c$
• Soundness: If $\Delta(y, L(x)) > \delta$, for all proofs $\pi$, $\Pr_{\rho \sim \{0,1\}^q}[V_L^{y \circ \pi}(x; \rho) = 1] < s$

We introduce a new proximity parameter $\delta < 1$, and the distance $\Delta(y, L(x))$ is defined as

if $x \in L$ and $\Delta(y, L(x)) = 1$ if $x \notin L$.

On one hand, the soundness criterion of PCPPs is a relaxation of the soundness of PCPs. Whereas, a PCP is required to reject (with high probability) every input that is not in the language, a PCPP is only required to reject input pairs $(x,y)$ in which the second element (i.e., $y$) is far from being suitable for the first element (i.e., $y$ is far from L(x)). That is, in a PCPP, nothing is required in the case that $y$ is close to $L(x)$ and yet $y \notin L(x)$. On the other hand, the query complexity of a PCPP is measured more stringently, as it accounts also for the queries to the input-part y (on top of the standard queries to the proof $π$). This should be contrasted with a standard PCP that has free access to all its input, and is only charged for access to an auxiliary proof.

Robust PCP

We now present a strengthening of the standard PCP soundness condition. Instead of asking that any proof is rejected with high probability, we ask that any proof is far from acceptance with high probability.

Definition

Given an input $x$ and a proof $\pi$, if we fix the random bits $\rho$, we have a local view $\pi(x, \rho)$. We define the accepting views as

A Language $L$ is in the complexity class RPCP$_{c, s, \sigma}[r, q]_\Sigma$ if there exists a polynomial-time probablistic oracle Turing machine called the RPCP verifier $V_L$ such that

• Completeness: If $x \in L$, there exists a proof $\pi$ such that $\Pr_{\rho \sim \{0,1\}^q}[V_L^\pi(x; \rho) = 1] > c$
• Soundness: If $x \notin L$, for all proofs $\pi$, $\Pr_{\rho \sim \{0,1\}^q}[\Delta(\pi(x, \rho), A(V, x, \rho))<\sigma] < s$

Here, the distance function $\Delta$ is defined similarly as in the case of PCPP. Note that PCP$_{c, s}[r, q] =$ RPCP$_{c, s, 0}[r, q]$, i.e., a vanilla PCP has $0$ robustness.

Proof Composition

To carry out proof composition, we will have an outer RPCP which has a small size, and an inner PCPP which uses a few queries. When the outer RPCP determines the oracle positions to query given random bits $\rho$, $\pi_{out}(x, \rho)$, the inner PCPP will verify that the selected positions are accepted, $V_{in}^{\pi_{out}(x, \rho), \pi_{in}^\rho}(x)=1$. The new proof will be the concatenation of $\pi_{out}$ and $\pi_{in}^\rho$ for all $\rho$. Note that we need the outer RPCP to be robust, because the inner PCPP only has soundness gurantee if $\pi_{out}(x, \rho)$ is far from accepting.

References

[1] CS 294 at UC Berkeley, Probabilistically Checkable and Interactive Proof Systems, Spring 2019, Website