1 Introduction

Most computation today is not done locally by a client, but instead is outsourced to third-party service providers in exchange for money. Trading computation for money brings up two problems—(a) how the client can guarantee correctness of the outsourced computation (without redoing the computation), and (b) how to design the payment scheme. The two problems are closely related: ideally, we want the payment scheme to be such that it incentivizes service providers to perform the computation correctly.

Interactive proofs (IP) are the most well-studied and widely-used theoretical framework to verify correctness of outsourced computation [7, 10, 11, 17, 18, 22, 28, 33]. In an IP, a weak client (or verifier) interacts with powerful service providers (or provers) to determine the correctness of their claim. At the end, the verifier probabilistically accepts or rejects the claim.Footnote 1 Interactive proofs guarantee that, roughly speaking, the verifier accepts a truthful claim with probability at least 2 / 3 (completeness) and no strategy of the provers can make the verifier accept a false claim with probability more than 1 / 3 (soundness).Footnote 2.

Rational proofs are payment-based interactive proofs for computation outsourcing which leverage the incentives of the service providers. In rational proofs, the provers act rationally in the game-theoretic sense, that is, they want to maximize their payment. The payment is designed such that when the provers maximize their payment, they also end up giving the correct answer. The model of rational proofs (\(\mathsf {RIP}\)) was introduced by Azar and Micali in [2]. Since then, many simple and efficient rational protocols have been designed [3, 9, 13, 23, 24, 26, 35].

While rational proofs provide strong theoretical guarantees, there are two main barriers that separate them from what is often desired in practice. First, many rational protocols require a polynomial-time verifier—but a “weak” client is unlikely to be able to spend (say) quadratic time or linear extra space on verification. Second, many of these protocols strongly rely on the rationality of the provers. An honest prover may receive only a fraction of a cent more than a dishonest prover, yet a rational prover is assumed to be incentivized by that small amount. However, service providers may not always be perfectly rational.

The goal of this paper is to give protocols that overcome these barriers.

Utility Gap. The strength of the guarantee provided by rational proofs is captured by the notion of utility gap. The high level idea behind utility gap is that provers who are not perfectly rational may not care about small losses in payments and may lazily give the incorrect answer. If a rational protocol has a utility gap of u, then the provers who mislead the verifier to an incorrect answer are guaranteed to lose at least 1 / u. (This is under a normalized budget of 1; if the budget is scaled up to B, such provers can be made to lose at least B / u.) Thus, protocols with small utility gap are sound even against provers with bounded rationality; that is, provers who are only sensitive to large losses.

In this paper, we design efficient rational protocols with strong utility gap—that is, polynomial, logarithmic, and even constant utility gap. In Section 5, we show when and how a noticeable utility gap of a rational protocol can be utilized to achieve the strong completeness and soundness guarantees of a classical proof.

Efficient Protocols. In this paper, we focus on designing rational protocols with very small overheads in terms of verification time, space, communication cost and number of rounds. In particular, we design constant-round rational protocols where the verification time and communication cost are logarithmic in the input size n. We also design single-round rational protocols that have only logarithmic overhead on the verifier’s use of space and randomness.

1.1 Results and Contributions

In this section, we summarize our results and contributions.

Time-Efficient Rational Proofs. We study the effect of different communication costs and an additional prover on the power of rational proofs with a highly time-efficient verifier. The utility gap of these protocols is polynomial.

  • Constant Communication. We show that multiple provers do not add any power when the communication complexity of the protocol is restricted to be extremely small—a constant number of bits. That is, we show that the class of languages that admit a multi-prover rational proof with a \(O(\log n)\)-time verifier and O(1) communication is exactly \(\mathsf {Uniform TC_0}\), which is the same as the power of single-prover version under the same costs [3, 23]. \(\mathsf {Uniform TC_0}\) is the class of constant depth, polynomial size uniform threshold circuits, that includes problems such as integer division and iterated multiplication [1, 25].

  • Logarithmic Communication. We show that any rational proof with polynomial communication can be simulated by a rational proof with logarithmic communication that uses an additional prover. Using this property, we improve the communication complexity of Azar and Micali’s [3] single-prover rational protocol and show that the class of languages that admit a two-prover rational proof with logarithmic communication is exactly the class of languages decidable by a polynomial time machine that can make polynomially many queries in parallel to an \(\mathsf {NP}\) oracle, denoted \(\mathsf {P_{||}^{NP}}\).Footnote 3 This is an important class (e.g., see [8, 30, 34]) and includes optimization problems such as maximum clique, longest paths, and variants of the traveling salesman problem.

Space-Efficient Rational Proofs. We achieve even better utility gap guarantees when the verifier’s use of space and randomness is extremely small—logarithmic, but its running time may be polynomial. In particular, we exactly characterize the class of single-round rational proofs with \(\gamma (n)\) utility gap and logarithmic space and randomness as the class of languages decidable by a polynomial-time machine that makes \(O(\gamma (n))\) queries to an \(\mathsf {NP}\) oracle, denoted \(\mathsf {P_{||}^{NP[\gamma (n)]}}.\) Even when \(\gamma (n) = O(1)\) this bounded-query class is still sufficiently powerful and contains many of the optimization problems mentioned above.

Rational Proofs with Completeness and Soundness Guarantees. Finally, we closely compare the two proof systems—rational and classical. We construct a condition on the expected payments of rational proofs which, if satisfied, turns them into a classical interactive proof with completeness and soundness guarantees. We first show how to convert a payment-based protocol for a language L to an accept-reject protocol (without payments) for L such that the expected payment of the former is exactly the probability with which the verifier accepts in the latter. We use this to prove that if the expected payments of all inputs \(x\in L\) are noticeably far away from that of all inputs \(x \notin L\), the rational protocol can be converted to a classical interactive protocol.

1.2 Additional Related Work

Azar and Micali [3] also characterize the classes \(\mathsf {Uniform TC_0}\) and \(\mathsf {P_{||}^{NP}}\). Their characterization of \(\mathsf {P_{||}^{NP}}\) requires polynomial communication, which we improve to logarithmic using a second prover. We also note that all protocols in [3] have a polynomial utility gap (under a constant budget).

Rational arguments, super-efficient rational proofs where the prover is restricted to be polynomial time, were introduced by Guo et al. [23]. Rational arguments for all languages in \(\mathsf {P}\) were given in [24]. Campanelli and Rosario [9] study sequentially composable rational proofs. Zhang and Blanton [35] design protocols to outsource matrix multiplications to a rational cloud.

The model of multi-prover rational interactive proofs was introduced by Chen et al. [13], where they study the power of the model in its full generality (that is, polynomial-time verifier and polynomial communication). In this paper, we restrict our focus on proofs with log-time verifiers and log-size communication.

Different variants of the rational-proof models have also been studied. Chen et al. [14] consider rational proofs where the rational provers are non-cooperative [14]. Inasawa and Kenji [27] consider rational proofs where the verifier is also rational and wants to minimize the payment to the provers.

Interestingly, the log-space verifier studied in this paper also happens to be a streaming algorithm, that is, the verifier does not need to look again at any input or message bits out of order. Thus, our space-efficient rational proofs are closely related to the work on streaming interactive proofs [11, 17, 18].

Refereed games is another multi-prover interactive-proof model that leads to game-theoretic characterizations of various complexity classes (e.g. [12, 20, 21, 29, 32]). The model of refereed games requires at least one honest prover.

2 Preliminaries

We begin by reviewing the model of rational proofs [2, 13].

Let L be a language, x be an input string and \(n= |x|\). An interactive protocol is a pair , where V is the verifier and is the vector of provers, and p(n) a polynomial in n. The goal of the verifier is to determine if \(x\in L\). In general, the verifier runs in time polynomial in n and uses polynomial space as well. In Sect. 3, the verifier’s running time is \(O(\log n)\). In Sect. 4, the verifiers may use polynomial time but are restricted to use \(O(\log n)\) space and randomness. The provers are computationally unbounded.Footnote 4

The verifier can communicate with each prover privately, but no two provers can communicate with each other. In a round, either each prover sends a message to the verifier, or the verifier sends a message to each prover, and these two cases alternate. Without loss of generality, provers send the first round of messages. The first bit of the first round is the answer bit, denoted by c, and indicates whether \(x\in L\); that is, \(x \in L\) iff \(c=1\). We define the communication of the protocol to be the maximum number of total bits transmitted (summed over all provers and all rounds) during the protocol.

Let r be the random string used by V. Let be the vector of all messages exchanged. At the end, the verifier computes the total payment to the provers, given by a payment function . We restrict the verifier’s budget to be constant, that is, \(R \in [0, 1]\) for convenience. We may use negative payments to emphasize penalties but they can shifted to be non-negative. The protocol (including the payment function R) is public knowledge.

The verifier outputs the answer bit c at the end of the protocol—thus the verifier always agrees with the provers.

Each prover \(P_i\) can choose a strategy \(s_{ij}:\{0,1\}^*\rightarrow \{0,1\}^*\) for each round j, which maps the transcript he has seen up until the beginning of round j to the message he sends in round j. Note that \(P_i\) does not send any message when j is even; in this case \(s_{ij}\) can be treated as a constant function. Let \(s_i = (s_{i1},\ldots , s_{ik})\) be the strategy vector of \(P_i\) and \(s = (s_1,\dots , s_{p(n)})\) be the strategy profile of the provers. Given any input x, randomness r and strategy profile s, we may write the vector of messages exchanged in the protocol more explicitly as .

The provers are cooperative and jointly act to maximize the total expected payment. Thus, before the protocol starts, the provers pre-agree on a strategy profile s that maximizes When and x are clear from the context, we write u(s) for .

Definition 1

([13]). For any language L, an interactive protocol is a rational interactive proof protocol for L if, for any \(x\in \{0, 1\}^*\) and any strategy profile s of the prover(s) such that \(u(s) = \max _{s'} u(s')\), \(c =1\) if and only if \(x\in L\).

Similar to classical proofs, single-prover rational interactive protocols, that is, when , are denoted by \(\mathsf {RIP}\). Multi-prover interactive protocols, where are denoted by \(\mathsf {MRIP}\). In this paper we study both single-prover and multi-prover rational proof protocols.

We use \(\mathrm {poly}(n)\) as a shorthand for a polynomial \(n^k\), for some constant k.

2.1 Utility Gap and Budget in Rational Proofs

In the above definitions, we assume that a prover is fully rational, and will give the correct answer for any increase in expected payment, no matter how small. However, a prover may be lazy, and unwilling to give the correct answer unless the correct answer increases its payment by some minimum amount.

The notion of utility gap captures the payment loss incurred by provers who misreport the answer bit. We recall the formal definition below.

Definition 2

([13]). Let L be a language with a rational proof protocol and let \(\gamma (n) \ge 0\). We say that has an \(\gamma (n)\)-utility gap if for any input x with \(|x|=n\), any strategy profile s of that maximizes the expected payment, and any other strategy profile \(s'\), where the answer bit \(c'\) under \(s'\) does not match the answer bit c under s, i.e., \(c'\ne c\), then \(u(s) - u(s') > {1}/{\gamma (n)}\).

Relationship Between Utility Gap and Budget. The budget is the total expected payment that a verifier can give in a protocol.

Utility gap and budget are closely related. To study utility gaps consistently, we maintain a fixed O(1) budget.Footnote 5 This is because utility gap scales naturally with the payment—a polynomial utility gap under a constant budget is the same as a constant utility gap under a sufficiently-large polynomial budget.

2.2 Analyzing Computational Costs of Rational Proofs

Our primary focus in this paper is analyzing the various computational costs of rational interactive proofs. The different parameters fall into two categories.

Verification Costs. A verifier has three main resources: running time, space usage and its randomness.

In Sect. 3, we focus on time-efficient \(O(\log n)\) time verifiers. Thus, their space and randomness is also \(O(\log n)\). We denote the class of languages that have time-efficient RIP protocols, that is, protocols with a \(O(\log n)\) time verifier as \(\mathsf {RIP}^t\). Multi-prover notation \(\mathsf {MRIP}^t\) is analogous. Similar to the literature on “probabilistically checkable proofs of proximity” (PCPPs) [5, 6, 33], we assume that the verifier has random access to the input string and the proof tape. Thus, if the messages sent by the provers are of size C(n) bits, the verifier needs at least \(O(\log C(n))\) time to index a random location of the transcript.

To achieve better utility gap, in Sect. 4, we restrict the verifier’s space usage and randomness, instead of its running time and consider verifiers that use \(O(\log n)\) space and \(O(\log n)\) randomness. We denote the class of languages that have an RIP protocol with space- and randomness-efficient verifiers, that is, verifiers with \(O(\log n)\) space and \(O(\log n)\) randomness as \(\mathsf {RIP}^{s,r}\).

Protocol Costs. A rational interactive proof protocol has three main ingredients: communication cost, number of rounds of interaction and utility gap.Footnote 6

In Section 3, we study the effect of varying the communication complexity of a protocol on its power when we have a logarithmic time verifier. The number of rounds in all the protocols in the paper is O(1).

We denote the class of languages that have an RIP protocol with communication cost C(n), number of rounds k(n) and utility gap \(\gamma (n)\) as \(\mathsf {RIP}[C(n), k(n), \gamma (n)]\). The multi-prover version is defined similarly.

3 Verification in Logarithmic Time

In this section we consider time-efficient verifiers that run in time logarithmic in the input size. We show that for time-efficient verifiers, access to multiple provers is fundamentally linked to the communication cost of the protocol: any single-prover protocol with high communication costs can be reduced to a communication-efficient multi-prover protocol. On the other hand, multiple provers give no extra power for communication-efficient protocols.

Since the utility gap of all the protocols in this section is polynomial in n, we drop it from the notation for simplicity. Thus, an RIP protocol with a \(O(\log n)\)-time verifier that has communication complexity C(n) and round complexity k(n) is denoted as \(\mathsf {RIP}^t[C(n), k(n)]\).

We omit the proofs, which can be found in the full version [15].

Constant Communication. We first show that multiple provers do not increase the power of a rational proof system when the communication complexity of the protocol is very small, that is, only O(1) bits. Recall that with a single prover, \(\mathsf {RIP}^t[O(\log n), O(\log n)] = \mathsf {RIP}^t[O(\log n), O(1)]= \mathsf {Uniform TC}_0 \) [3, 23].

Theorem 1

\(\mathsf {MRIP}^t[O(1), O(1)] = \mathsf {Uniform TC}_0.\)

Logarithmic and Polynomial Communication. We characterize the power of MRIP protocols with \(O(\log n)\)-time verification, when the communication complexity of the protocol is logarithmic and polynomial in n.

Theorem 2

\(\mathsf {MRIP}^t[\mathrm {poly}(n), \mathrm {poly}(n)] = \mathsf {MRIP}^t[O(\log (n)), O(1)] =\mathsf {P_{||}}^{\mathsf {NP}}.\)

Azar and Micali [3] characterized the class \(\mathsf {P_{||}^{NP}}\) in terms of single-prover rational proofs with \(O(\log n)\) verification and \(O(\mathrm {poly}(n))\) communication. In particular, they proved that \(\mathsf {RIP}[O(\mathrm {poly}(n)), O(1)] = \mathsf {P_{||}^{NP}}\).

To prove Theorem 2, we first show that using two provers reduces the communication complexity of the RIP protocol for \(\mathsf {P_{||}^{NP}}\) exponentially. In fact, we show prove a more general statement—any MRIP protocol (thus any RIP protocol as well) with a logarithmic time verifier and polynomial communication can be simulated using two provers, five rounds and logarithmic communication.

Lemma 1

A MRIP protocol with p(n) procers, k(n) rounds, verification complexity T(n), and communication complexity of C(n) can be simulated by an MRIP protocol with 2 provers, 5 rounds, verification complexity \(O(T(n) + \log C(n))\) and communication complexity \(O(T(n) + \log C(n))\).

The main idea behind the proof of Lemma 1 is to use the first prover to obtain the entire “effective transcript” of the original protocol. An effective transcript is all the bits that, for a given randomness r, a log-time time verifier ever accesses in the original protocol. The size of the effective transcript is at most T(n). Then, the second prover is used to verify the correctness of this transcript.

Lemma 1 demonstrates the importance of two provers over one to save on communication cost in rational proofs.

Corollary 1

\(\mathsf {RIP}^t[O(\mathrm {poly}(n)), O(1) ] = \mathsf {P_{||}^{NP}} \subseteq \mathsf {MRIP}^t[ O(\mathrm {poly}(n)), O(\mathrm {poly}(n)] \subseteq \mathsf {MRIP}^t[O(\log n), O(1) ]. \)

To complete the proof Theorem 2, we show the following upper bound.

Lemma 2

\(\mathsf {MRIP}^t[ O(\log (n)), O(1)] \subseteq \mathsf {P_{||}^{NP}}.\)

4 Verification in Logarithmic Space

The protocols in Section 3 have a polynomial utility gap. For a constant budget this means that the provers who mislead the verifier to an incorrect answer lose at least \(1/\mathrm {poly}(n)\) of their expected payment.

As utility gap is analogous to the soundness gap in classical proofs, which is constant (independent of n), it is desirable to have rational protocols with constant utility gap as well.

Constant utility gap is difficult to achieve when the verifier is \(O(\log n)\) time and cannot even read the entire input. This is true even for classical proofs with a \(O(\log n)\)-time verifier where the soundness conditioned is weakened to design PCPPs [5, 6, 33]. In particular, the soundness guarantees of such proofs depend on how far (usually in terms of hamming distance) the input string x is from the language L. We note that all existing \(O(\log n)\)-time rational proofs [3, 23, 24] have polynomial utility gap (under a constant budget).

To design protocols with a strong utility gap such as logarithmic or constant, in this section we consider verifier’s that use only \(O(\log n)\) space and randomness.

Let \(\gamma (n)\) be a polynomial-time computable and polynomially bounded function, e.g., O(1), \(\log n\), or \(\sqrt{n}\). We prove the characterization for utility gap \(\gamma (n)\).

Theorem 3

Let \(\mathsf {P_{||}^{\mathsf {NP[\gamma (n)]}}}\) be a polynomial-time Turing machine that can make \(O(\gamma (n))\) non-adaptive queries to an \(\mathsf {NP}\) oracle. This class is equivalent to the class of languages that have a one-round RIP protocol with a logspace verifier, polynomial communication and \(\gamma (n)\)-utility gap. That is,

$$\begin{aligned} \mathsf {RIP}^{r,s} [\mathrm {poly}(n), 1, \gamma (n)] = \mathsf {P}_{||}^{\mathsf {NP[\gamma (n)]}}. \end{aligned}$$

First, we give a space-efficient RIP for the class \(\mathsf {NP}\) using the log-space interactive proof for the language given by Condon and Ladner [16] as a blackbox.

Lemma 3

\(\mathsf {NP} \in \mathsf {RIP}^{r,s} [\mathrm {poly}(n), 1, \gamma (n)] .\)

For the lower bound, we use a different but equivalent complexity class. Let \(\mathbf {L}_{||}^{\mathsf {NP[\gamma (n)]}}\) be a logarithmic space machine that can make \(O(\gamma (n))\) non-adaptive queries to an \(\mathsf {NP}\) oracle. Wagner [34] showed that \( \mathbf {L}_{||}^{\mathsf {NP[\gamma (n)]}} = \mathsf {P_{||}^{NP[\gamma (n)]}}\).

Lemma 4

\(\mathsf {P_{||}^{NP[\gamma (n)]}}=\mathbf {L}_{||}^{\mathsf {NP[\gamma (n)]}} \subseteq \mathsf {RIP}^{r,s} [\mathrm {poly}(n), 1, \gamma (n)].\)

The main idea of the proof is that the prover sends all messages (the overall answer bit, the answer bit of all NP queries and their proofs) in one round. The verifier checks all oracle queries simultaneously using the blackbox protocol [16] and scales the payment appropriately; see full version [15] for the proof.

To complete the proof of Theorem 3 we prove the following upper bound.

Lemma 5

\(\mathsf {RIP}^{r,s} [\mathrm {poly}(n), 1, \gamma (n)]\subseteq \mathsf {P_{||}^{NP[\gamma (n)]}}.\)

5 Relationship Between Classical and Rational Proofs

In this section, we show under what conditions does a rational interactive proof reduces to a classical interactive proof. The results in this section are stated in terms of the multi-prover model (that is, \(\mathsf {MRIP}\) and \(\mathsf {MIP}\)) which is more general, and thus they also hold for the single prover model (that is, \(\mathsf {RIP}\) and \(\mathsf {IP}\)).

To compare the two proof models, we explore their differences. In rational interactive proofs, the provers are allowed to claim \(c=1\) (that is, \(x\in L\)) or \(c=0\) (that is, \(x\notin L\)) based on their incentives.Footnote 7 Furthermore, for a particular input x of size n, if the provers’ claim c about x is incorrect, they lose at least a \(1/\gamma (n)\), where \(\gamma (n)\) is the utility gap.

On the other hand, in classical proofs, the provers are only allowed to prove \(x\in L\). Furthermore, given completeness and soundness parameters c and s respectively, where \(0 \le s < c \le 1\), for any \(x \in L\), there exists a strategy such that V accepts with probability \(\ge c\) and for any \(x \notin L\), for any strategy V rejects with probability \(\le s\). Thus, given L, the guarantees are independent of x.

In this section, we show when a rational proof reduces to a classical proof. Intuitively, this happens when the utility gap guarantee of a rational protocol is made to hold for all x and in particular, it is enforced to be the gap between the expected payments for all \(x\in L\) and all \(x\notin L\).

We first show that without loss of generality we can restrict the payments of the provers in a rational proof protocol to be either 1 or 0, where 1 corresponds to “accept” and 0 to “reject” respectively.

Lemma 6

Any MRIP protocol with payment \(R \in [0,1]\) and utility gap \(\gamma (n)\) can be simulated by a MRIP protocol with payment \(R' \in \{0, 1\}\) and utility gap \(\gamma (n)/2\). In particular, for any strategy s and any input x,

\(V'\) uses \(1 + \lceil \log _2 \gamma (n)\rceil \) more random bits than V.

In the proof of Lemma 6, \(V'\) simulates V, but instead of giving a payment \(R\in [0,1]\), it gives a payment of 1 with probability R, and 0 otherwise. This preserves the expected reward for each transcript (and thus for each strategy).

Given any rational protocol with zero-one payments, we note that it immediately gives us an accept-reject protocol such that for a given x, the probability that the verifier accepts is exactly the expected payment of the original protocol. More formally let be a rational protocol with \(R \in \{0,1\}\) and utility gap \(\gamma (n)\). Let be defined as follows: \(V'\) simulates V, ignores the answer bit c, and if the payment in is \(R=1\) then accept, else reject.

Thus, for a given input string x, the expected payment in is equal to the probability that \(V'\) accepts in . That is,

(1)

Furthermore, satisfies the following: for any \(x\in L\), let \(s^*\) denote the optimal strategy of the provers , that is, \(s^*\) maximizes their expected payment. Then for following \(s^*\), \(V'\) accepts with probability exactly . Furthermore, we know from the utility gap condition that for any \(x \notin L\), for any strategy \(s'\), the probability that \(V'\) accepts is at most , that is, the probability that \(V'\) accepts is at most \(s(x, n) < c(x,n)- 1/\gamma (n)\). Similar guarantees hold for any \(x\notin L\).

However, if we want to be an interactive proof protocol in the classical sense, that is, with completeness and soundness guarantees that hold for all \(x \in L\) and for all \(x\notin L\) respectively, we need to impose restrictions on the expected payment function of the rational protocol.

Theorem 4

Let be an MRIP protocol for a language L such that

(2)

where x is any input of length n, \(s^*\) is the strategy of the provers that maximizes their expected payment in and \(\gamma (n)\) is any function such that \(\gamma (n)>1\) and \(\gamma = O(\mathrm {poly}(n))\). Then, can be simulated by a MIP protocol for L.

We prove this theorem in two parts. First, we show prove the following lemma which proves Theorem 4 with weak completeness and soundness guarantees.

Lemma 7

Let be an MRIP protocol for a language L that satisfies the condition 2 in Theorem 4. Then, can be simulated by MIP protocol with completeness and soundness parameters c(n) and s(n) respectively such that \(c(n) > s(n) + 1/2\gamma (n)\) and \(c(n), s(n)\ge 0\).

We amplify the “gap” of an MIP by repeating the protocol sufficiently many times and then using Chernoff bounds. The techniques are mostly standard, although the parameters must be set carefully to deal with the case \(s(n) = 0\).

Lemma 8

Given an MIP protocol for a language L, with completeness \(c(n) > 0\) and soundness \(s(n)\ge 0 \) such that \(c(n) > s(n) + 1/\gamma '(n)\) for some \(\gamma '(n)>1\) and \(\gamma ' =O (\mathrm {poly}(n))\), can be converted to an MIP protocol for L with completeness at least \(1- 1/\mathrm {poly}(n)\) and soundness at most \(1/\mathrm {poly}(n)\).

Remark 1

The repetition of the MIP protocol to amplify its completeness and soundness guarantee used in Lemma 8 is not efficient as it blows up the number of rounds. There exist more efficient techniques to amplify IP guarantees by parallel repetition that can be used instead; for example, see [4, 19, 31].