AM with Multiple Merlins

Introduction

The $\mathsf{PCP}$ characterization of $\mathsf{NP}$ , with the resulting hardness of approximation results, is one of the great achievements of computational complexity. Leading up to this work was another landmark result, the 1991 theorem of Babai, Fortnow, and Lund that $\mathsf{MIP}=\mathsf{NEXP}$, where $\mathsf{MIP}$ is Multi-Prover Interactive Proofs and $\mathsf{NEXP}$ is Nondeterministic Exponential Time. Both of these results can be paraphrased as characterizing the hardness of a certain computational problem from game theory: estimating the value of a two-player cooperative game with simultaneous moves. Such games are known in the complexity community as two-prover games, and in the quantum information community as nonlocal games. From now on, we will use the term two-prover games.

finite question sets $X,Y$ and answer sets $A,B$,

a probability distribution $\mathcal{D}$ over question pairs $\left(x,y\right)\in X\times Y$, and

a verification function $V:X\times Y\times A\times B\rightarrow\left[0,1\right]$.In most of the actual games we will consider, $V$ will take values in $\left\{0,1\right\}$ only. However, the possibility of real $V$ is needed for full generality.

The value of the game, denoted $\omega\left(G\right)$, is the maximum, over all pairs of response functions $a:X\rightarrow A$ and $b:X\rightarrow B$, of

The interpretation is this: the game $G$ involves a verifier/referee Arthur, as well as two cooperating provers Merlin1 and Merlin2, who can agree on a strategy in advance but cannot communicate once the game starts. First Arthur chooses a pair of questions $\left(x,y\right)$ from $\mathcal{D}$, and sends $x$ to Merlin1 and $y$ to Merlin2. The Merlins then send back responses $a=a\left(x\right)$ and $b=b\left(y\right)$ respectively.Because of convexity, we can assume without loss of generality that both Merlins use deterministic strategies. Finally, Arthur declares the Merlins to have “won” with probability equal to $V\left(x,y,a,b\right)$. Then $\omega\left(G\right)$ is just the probability that the Merlins win if they use an optimal strategy.

It is not hard to show that computing the exact value of a two-prover game is $\mathsf{NP}$-hard. The PCP Theorem can be interpreted as saying that even to approximate the value to within an additive constant is also $\mathsf{NP}$-hard. To make this precise, we can define the classes $\mathsf{PCP}$ and $\mathsf{MIP}$ as those decision problems polynomial-time reducible to approximating the value of a two-prover game. The difference between the classes is that for PCP’s, the reduction computes an explicit description of the game, whereas for $\mathsf{MIP}$, the description is implicit.

To be more precise, we start with a decision problem $L$. Given an instance $I$ of $L$, a reduction constructs a two-prover game $G_{I}$ with the following properties:

(Completeness) If $I\in L$ then $\omega\left(G_{P}\right)\geq 2/3$.

(Soundness) If $I\not\in L$ then $\omega\left(G_{P}\right)\leq 1/3$.

(Efficiency) In the “explicit” case, the sets $X,Y,A,B$ can be generated in time polynomial in $n=\left|I\right|$, the distribution $\mathcal{D}$ can be described in polynomial time as the uniform distribution over some subset of $X\times Y$, and and the verification procedure $V(x,y,a,b)$ can be generated in polynomial time as a table of size $\left|X\right|\times\left|Y\right|\times\left|A\right|\times\left|B\right|$. In the “implicit” case, $X,Y,A,B$ are sets of $\operatorname*{poly}\left(n\right)$-bit strings, $\mathcal{D}$ can be described as a probabilistic polynomial-time sampling procedure that returns a pair $(x,y)\in X\times Y$, and the verification function $V(x,y,a,b)$ can be computed in polynomial time.

The class $\mathsf{PCP}$ then consists of all decision problems that can be reduced explicitly to two-prover games, while $\mathsf{MIP}$ consists of all decision problems that can be reduced implicitly to two-prover games. As frequently happens, switching from explicit to implicit representations causes us to “jump up” in complexity by an exponential. The dual theorems $\mathsf{PCP}=\mathsf{NP}$ and $\mathsf{MIP}=\mathsf{NEXP}$ bear out this general pattern.

The hardness of approximating two-prover games can in turn be used to show hardness of approximation for many constraint-satisfaction problems. Better trade-offs in the parameters of the reduction and specific kinds of verification procedure give tighter hardness of approximation results for a wide variety of particular combinatorial optimization problems. So the study of two-prover games did not end with the PCP Theorem.

In this paper, we consider the following restriction of two-prover games:

What if we demand that Arthur’s challenges to Merlin1 and Merlin2 be independent? In other words, what if the distribution $\mathcal{D}$ is simply the uniform distribution over $X\times Y$?We could also let $\mathcal{D}$ be an arbitrary product distribution, but we don’t gain any interesting generality that way: Arthur might as well just send Merlin1 and Merlin2 the uniform random bits he would’ve used to generate $x\in X$ and $y\in Y$ respectively.

In the PCP literature, two-prover games where $\mathcal{D}$ is uniform over $X\times Y$ are called “free” games, and have sometimes been studied as an easier-to-analyze special case of general games . Free games are also tightly connected to dense instances of constraint satisfaction problems. In this paper, we consider approximating the values of free games as an interesting computational problem in its own right, and one that has not received explicit attention. As far as we know, we are the first to study the complexity of this problem directly, and to formulate complexity classes of problems reducible to free games.

In more detail, the restriction to free games gives us an analogue of “public-coin” protocols in the single-prover interactive proof setting. This corresponds to the original definition of the class $\mathsf{AM}$, so we use a version of $\mathsf{AM}$ notation. We consider $\mathsf{AM}\left(2\right)$, or two-prover Arthur-Merlin: the class of all languages that admit two-prover, two-round interactive proof systems, in which Arthur’s challenges to the Merlins are independent, uniformly-random $\operatorname*{poly}\left(n\right)$-bit strings. In other words, $\mathsf{AM}(2)$ is the class of problems implicitly reducible to approximating the value of a free game. Clearly

We want to know: what is the true power of $\mathsf{AM}\left(2\right)$? Is it more powerful than single-prover $\mathsf{AM}$? Is it less powerful than $\mathsf{MIP}$? We will also be interested in the complexity of approximating the values of explicit free games.

As we’ll discuss in Section 4, an additional motivation to study $\mathsf{AM}\left(2\right)$ comes from difficult analogous questions about quantum multi-prover proof systems, and specifically about the quantum complexity class $\mathsf{QMA}\left(2\right)$. Our results could shed light on $\mathsf{QMA}\left(2\right)$, by showing how many questions about it get resolved in a simpler “classical model situation.”

Our Results

We have two main sets of results: upper bounds, showing that the value of a free game can be approximated in quasipolynomial time and translating that into complexity class containments; and hardness results, giving almost matching lower bounds for this problem under the Exponential Time Hypothesis (ETH). Thus, assuming only the ETH, we show both that free games are exponentially easier than general two-prover games, and also they still remain nontrivial, out of reach for polynomial-time algorithms.

Let FreeGameε be the problem of approximating the value of a free game to error $\pm\varepsilon$:

Given as input a description of a free game $G=\left(X,Y,A,B,V\right)$, estimate $\omega\left(G\right)$ to within additive error $\pm\varepsilon$. (Here $n$, the input size, is $\left|X\right|\left|Y\right|\left|A\right|\left|B\right|$, and $\varepsilon$ is an arbitrarily small constant if not specified explicitly.)

We give a quasipolynomial-time algorithm for FreeGameε:

FreeGameε is solvable in deterministic time $n^{O(\varepsilon^{-2}\log n)}$.

While this is the first algorithm explicitly for FreeGameε, there is some directly-related algorithmic work. After learning of our results (but before this paper was written), Brandao and Harrow gave an algorithm for FreeGameε with the same running time as ours, but using interestingly different techniques. (Our algorithm is purely combinatorial, whereas theirs uses linear programming relaxation.) Also, Barak et al. gave a quasipolynomial-time approximation algorithm for the related problem of approximating the values of dense CSPs with polynomial-sized alphabets.

In the implicit setting, Theorem 3 implies that $\mathsf{AM}\left(2\right)\subseteq\mathsf{EXP}$, which improves on the trivial upper bound of $\mathsf{NEXP}$. However, by building on the result of Barak et al. mentioned above, we are able to prove a stronger result, which completely characterizes $\mathsf{AM}\left(2\right)$:

We can even generalize Theorem 4 to handle any polynomial number of Merlins:

$\mathsf{AM}\left(k\right)=\mathsf{AM}$ for all $k=\operatorname*{poly}\left(n\right)$.

Thus, in the complexity class setting, it is really the correlation between queries that makes multiple provers more powerful than a single prover.

2 Hardness Results

Seeing just the above, one might conjecture that the values of free games are approximable in polynomial time. But surprisingly, we give strong evidence that this is not the case.

To show the power of free games, we give a nontrivial reduction from 3Sat to FreeGame. Equivalently, we show that there exists a nontrivial $\mathsf{AM}\left(2\right)$ protocol: even if Arthur’s challenges are completely independent, two Merlins can be more helpful to him than one Merlin. In particular, given a 3Sat instance $\varphi$, let the size of $\varphi$ be the number of variables plus the number of clauses. Then:

For some constant $\varepsilon>0$, there exists a reduction running in time $2^{\widetilde{O}(\sqrt{n})}$ that maps 3Sat instances of size $n$ to FreeGameε instances of size $2^{\widetilde{O}(\sqrt{n})}$ (where the $\widetilde{O}$ hides polylogarithmic factors).

In other words, there is a protocol whereby Arthur can check that a 3Sat instance of size $n$ is satisfiable, by exchanging only $\widetilde{O}(\sqrt{n})$ bits with the Merlins—i.e., sending $\widetilde{O}(\sqrt{n})$-bit challenges and receiving $\widetilde{O}(\sqrt{n})$-bit responses. The protocol has perfect completeness and a $1$ vs. $1-\varepsilon$ completeness/soundness gap, for some fixed constant $\varepsilon>0$. Since the first step we use is the PCP Theorem, by composing our main protocol with various PCP constructions, we can get reductions with different quantitative tradeoffs between reduction time, completeness, soundness, and alphabet size.

One corollary of Theorem 6 is that, if FreeGame is in $\mathsf{P}$, then 3Sat is in $\mathsf{TIME}(2^{\widetilde{O}(\sqrt{n})})$. Since 3Sat is complete under quasilinear-time reductions for $\mathsf{NTIME}(n)$, the same holds for any problem in nondeterministic linear time. As a second corollary, we get a lower bound on the time to approximate FreeGame assuming the ETH. This lower bound almost matches the upper bounds described in Section 2.1. To be more precise, recall the Exponential Time Hypothesis (ETH) of Impagliazzo and Paturi :

Any deterministic algorithm for 3Sat requires $2^{\Omega\left(n\right)}$ time. (There is also the Randomized ETH, which says the same for bounded-error randomized algorithms.)

Assuming the (randomized) ETH, any (randomized) algorithm for FreeGameε requires $n^{\widetilde{\Omega}(\varepsilon^{-1}\log n)}$ time, for all $\varepsilon\geq 1/n$ bounded below some constant.

Again, by considering various PCP constructions, we get a variety of hardness results for many interesting versions and ranges of parameters for the FreeGame problem.

We can further reduce FreeGame to the problem of approximating dense CSPs, where an arity $k$ CSP is considered dense if it contains constraints for a constant fraction of all $k$-tuples of variables. We thus get the following hardness result for dense CSPs.

Assuming the ETH, the problem of approximating a dense $k$-CSP (constraint satisfaction problem) with a polynomial-size alphabet, to constant additive error, requires $n^{\widetilde{\Omega}\left(\log n\right)}$ time, for any $k\geq 2$.

Corollary 9 almost matches the upper bound of Barak et al. , explaining for the first time why Barak et al. were able to give a quasipolynomial-time algorithm for approximating dense CSPs, but not a polynomial-time one.

As another application of our hardness result for FreeGame, Brandao and Harrow were recently able to use it to prove that approximating the values of certain entangled games requires $n^{\widetilde{\Omega}\left(\log n\right)}$ time, assuming the ETH.See for the precise definition of the entangled games they consider. Briefly, though, the games involve a large number of provers, of whom two are selected at random to receive challenges (the other provers are ignored).

Detailed Overview of Results

We now proceed to more detailed overview of our results and the techniques used to prove them. Here, as in the technical part of the paper, we first describe our hardness results for FreeGame (or equivalently, $\mathsf{AM}\left(2\right)$ protocols for 3Sat), and then our approximation algorithms (or equivalently, limitations of $\mathsf{AM}\left(k\right)$ protocols).

The idea of our 3Sat protocol is simple. First Arthur transforms the 3Sat instance $\varphi$ into a PCP, so that it’s either satisfiable or far from satisfiable. For this to work, we need a highly-efficient PCP theorem, which produces instances of near-linear size. Fortunately, such PCP theorems are now known. Depending on the desired parameters, we will use either the theorem of Dinur (which produces 3Sat instances of size $n\operatorname*{polylog}n$ with a small constant completeness/soundness gap), or that of Moshkovitz and Raz (which produces $2$-CSP instances of size $n\cdot 2^{\left(\log n\right)^{1-\Omega(1)}}$ with completeness/soundness gap arbitrarily close to $1$).

Suppose for now that we use the PCP theorem of Dinur . Then next, Arthur runs a variant of the so-called clause/variable game, which we define below.

Given a 3Sat instance $\varphi$, consisting of $n$ variables $x_{1},\ldots,x_{n}$ and $m$ clauses $C_{1},\ldots,C_{m}$, the clause/variable game $G_{\varphi}$ is defined as follows. Arthur chooses an index $i\in\left[m\right]$ uniformly at random, then chooses $j\in\left[n\right]$ uniformly at random conditioned on $x_{j}$ or $\urcorner x_{j}$ appearing in $C_{i}$ as a literal. He sends $i$ to Merlin1 and $j$ to Merlin2. Arthur accepts if and only if

Merlin1 sends back a satisfying assignment to the variables in $C_{i}$, and

Merlin2 sends back a value for $x_{j}$ that agrees with the value sent by Merlin1.

Let $\operatorname*{SAT}\left(\varphi\right)\in\left[0,1\right]$ be the maximum fraction of clauses of $\varphi$ that can be simultaneously satisfied. Then clearly the clause/variable game has perfect completeness: that is, if $\operatorname*{SAT}\left(\varphi\right)=1$ then $\omega\left(G_{\varphi}\right)=1$. The following well-known proposition shows that the game also has constant soundness.

If $\operatorname*{SAT}\left(\varphi\right)\leq 1-\varepsilon$, then $\omega\left(G_{\varphi}\right)\leq 1-\varepsilon/3$.

Proof. Assume without loss of generality that Merlin2 answers according to a particular assignment $x=\left(x_{1},\ldots,x_{n}\right)$. By hypothesis, $x$ violates the clause $C_{i}$ with probability at least $\varepsilon$ over $i$. And if $x$ violates $C_{i}$, then regardless of what Merlin1 does, Arthur rejects with probability at least $1/3$—since Merlin1’s assignment to $C_{i}$ either violates $C_{i}$, or else disagrees with $x$ (which Arthur detects with probability at least $1/3$ over the variable sent to Merlin2).

Also, given any two-prover game $G=\left(X,Y,A,B,\mathcal{D},V\right)$, let $G^{k}$ be the $k$-fold parallel repetition of $G$: that is, the game where Arthur

draws $\left(x_{1},y_{1}\right),\ldots,\left(x_{k},y_{k}\right)$ independently from $\mathcal{D}$,

sends $x_{1},\ldots,x_{k}$ to Merlin1 and $y_{1},\ldots,y_{k}$ to Merlin2,

receives responses $a_{1},\ldots,a_{k}\in A$ from Merlin1 and $b_{1},\ldots,b_{k}\in B$ from Merlin2, and then

accepts with probability equal to $\prod_{i=1}^{k}V\left(x_{i},y_{i},a_{i},b_{i}\right)$.

Then the famous Parallel Repetition Theorem asserts that $\omega(G^{k})$ decreases exponentially with $k$:

If $\omega\left(G\right)\leq 1-\varepsilon$, then

Unfortunately, neither the original clause/variable game $G_{\varphi}$, nor its parallel repetition $G_{\varphi}^{k}$, work in the setting of $\mathsf{AM}\left[2\right]$. For both games rely essentially on correlation between the clause(s) sent to Merlin1 and the variable(s) sent to Merlin2. To eliminate the need for correlation, we use a new form of repetition that we call birthday repetition.

2 Approximation Algorithms for Free Games

Our second set of results aims at showing that a square-root savings in communication, as achieved by our $\mathsf{AM}\left(2\right)$ protocol for 3Sat, is the best that any such protocol can provide. More formally, we prove the following set of four interrelated results:

The FreeGameε problem is solvable deterministically in $\left(\left|X\right|\left|A\right|\right)^{O(\varepsilon^{-2}\log\left|Y\right|\left|B\right|)}=n^{O(\varepsilon^{-2}\log n)}$ time. (There is also a randomized algorithm that uses $\left|X\right|\cdot\left|A\right|^{O(\varepsilon^{-2}\log\left|Y\right|\left|B\right|)}$ time.)

Any $\mathsf{AM}\left(2\right)$ protocol involving $p\left(n\right)$ bits of communication can be simulated in $2^{O(p\left(n\right)^{2})}\operatorname*{poly}\left(n\right)$ time (deterministically, if Arthur’s verification procedure is deterministic, and probabilistically otherwise). So in particular, $\mathsf{AM}\left(2\right)\subseteq\mathsf{EXP}$, improving the trivial upper bound of $\mathsf{NEXP}$. (As we point out, a closer analysis improves the upper bound to $\mathsf{AM}\left(2\right)\subseteq\mathsf{AM}^{\mathsf{NP}}$.)

Assuming the Randomized ETH, any constant-soundness $\mathsf{AM}\left(2\right)$ protocol for 3Sat must use $\Omega(\sqrt{n})$ communication. (In more detail, such a protocol must use $\Omega(\sqrt{\varepsilon n})$ communication if its completeness/soundness gap is $1$ vs. $1-\varepsilon$, and $\Omega(\sqrt{n\log 1/\delta})$ communication if its gap is $1$ vs. $\delta$. Also, if Arthur’s verification procedure is deterministic, then it suffices to assume the standard ETH.)

$\mathsf{AM}\left(2\right)=\mathsf{AM}$. (Of course, this supersedes our $\mathsf{AM}\left(2\right)\subseteq\mathsf{EXP}$ and $\mathsf{AM}\left(2\right)\subseteq\mathsf{AM}^{\mathsf{NP}}$ results.)

In Section 7.1, we provide a self-contained proof for result (1), and then use (1) to deduce (2) and (3). The idea of our approximation algorithm is to sample a small random subset $S\subset X$ of the questions to Merlin1. We then brute-force search over all possible strategies $\alpha:S\rightarrow A$ for the questions in $S$. For each such strategy $\alpha$, we find the optimal response $b_{\alpha}:Y\rightarrow B$ of Merlin2 to that $\alpha$, and then the optimal response $a_{\alpha}:X\rightarrow A$ of Merlin1 to $b_{\alpha}$ on his full question set $X$. A simple probabilistic analysis then shows that, provided we take $\left|S\right|=\Omega\left(\varepsilon^{-2}\log\left|Y\right|\left|B\right|\right)$, at least one of these “induced” strategy pairs $\left(a_{\alpha},b_{\alpha}\right)$ must achieve value within $\varepsilon$ of the optimal value $\omega\left(G\right)$. Similar ideas have been used before in other approximation algorithms: for example, in that of Lipton, Markakis, and Mehta for finding approximate Nash equilibria.

Once we have an $n^{O\left(\varepsilon^{-2}\log n\right)}$-time approximation algorithm for FreeGameε, the containment $\mathsf{AM}\left(2\right)\subseteq\mathsf{EXP}$ follows almost immediately. We also sketch an improvement to $\mathsf{AM}\left(2\right)\subseteq\mathsf{AM}^{\mathsf{NP}}$, which is obtained by modifying our approximation algorithm so that it fits into the property-testing framework of Goldreich, Goldwasser, and Ron . As for the optimality of our 3Sat protocol, we simply need to observe that, if we had a protocol that used $o(\sqrt{n})$ communication, then it would give rise to a free game $G$ of size $2^{o(\sqrt{n})}$, whose value $\omega\left(G\right)$ we could estimate in $2^{o\left(n\right)}$ time by using our quasipolynomial-time approximation algorithm. But that would let us decide 3Sat in $2^{o\left(n\right)}$ time, contradicting the Exponential Time Hypothesis.

For result (4), we wish to go further, and show that any two-Merlin protocol can be simulated using one Merlin: that is, $\mathsf{AM}\left(2\right)=\mathsf{AM}$. Here we appeal to a powerful line of earlier work on subsampling for dense CSPs. Specifically, Alon et al. showed in 2002 that, given any $k$-ary constraint satisfaction problem $\varphi$ over $n$ Boolean variables, one can estimate the maximum number of constraints in $\varphi$ that can be simultaneously satisfied, to within additive error $\pm\varepsilon\binom{n}{k}$, by simply throwing away all the variables except for a random set $I$ of size $\operatorname*{poly}\left(1/\varepsilon\right)$, and then using brute-force search to find an optimal assignment to $\varphi_{I}$, the restriction of $\varphi$ to $I$.

To build intuition, it is easy to satisfy $\varphi_{I}$ at least as well as we can satisfy $\varphi$, with high probability over $I$. To do so, simply start with an optimal global assignment $x$ for $\varphi$; then restrict $x$ to the variables in $I$ and apply a Chernoff bound. The hard part is to show that $\varphi_{I}$ cannot be satisfied much better than the full instance $\varphi$ was. Conversely, one needs to show that, given a collection of “local assignments,” involving just $\operatorname*{poly}\left(1/\varepsilon\right)$ variables at a time, one can “patch them together” into a global assignment that is almost as good as the local ones.

In later work, Barak et al. proved a more general result, which removed Alon et al.’s assumption that the alphabet is Boolean. Their result lets us approximate the value of any dense $k$-CSP $\varphi$ over the finite alphabet $\Sigma$ to within additive error $\pm\varepsilon\binom{n}{k}$, by solving a random sub-instance on $\operatorname*{poly}\left(1/\varepsilon\right)\cdot\log\left|\Sigma\right|$ variables.

To see the relevance of this work to free games, we simply need to observe that FreeGame can be directly encoded as a dense CSP. Given a free game $G=\left(X,Y,A,B,V\right)$, we can create variables $\left(a\left(x\right)\right)_{x\in X}$ and $\left(b\left(y\right)\right)_{y\in Y}$ over the alphabets $A$ and $B$ respectively, and then for all $\left(x,y,a,b\right)\in X\times Y\times A\times B$, add a number of constraints setting $a\left(x\right)=a$ and $b\left(y\right)=b$ that is proportional to $V\left(x,y,a,b\right)$. Once we do this, the result of Barak et al. implies a subsampling theorem for free games—saying that the value of any free game $G$ can be well-approximated by the value of a logarithmic-sized random subgame. And this, in turn, readily implies that $\mathsf{AM}\left(2\right)=\mathsf{AM}$. For given any $\mathsf{AM}\left(2\right)$ protocol, we can simulate the protocol in $\mathsf{AM}$ by having Arthur execute the following steps:

Choose random subsets $S,T$ of $\operatorname*{poly}\left(n\right)$ questions to Merlin1 and Merlin2 respectively.

Ask a single Merlin to send him responses to all questions in $S$ and $T$.

Check the responses, for all possible question pairs $\left(x,y\right)\in S\times T$.

The soundness of this approach follows from the subsampling theorem, which says that if Merlins had no winning strategy in the original $\mathsf{AM}\left(2\right)$ protocol, then with high probability, they have no winning strategy even when restricted to the tiny subset of questions $S\times T$.

One might ask: if existing results on dense CSPs can be used to show that $\mathsf{AM}\left(2\right)=\mathsf{AM}$, then why do we “reinvent the wheel,” and provide self-contained proofs for weaker results such as $\mathsf{AM}\left(2\right)\subseteq\mathsf{EXP}$? One answer is that the dense CSP results do not give good dependence on the error. For example, those results imply that FreeGameε can be solved in $n^{O(\varepsilon^{-\Lambda}\log n)}$ time for some large and unspecified constant $\Lambda$, but not that it can be solved in $n^{O(\varepsilon^{-2}\log n)}$ time. And we actually care about the dependence on $\varepsilon$, for at least two reasons. First, we wish to make an analogy with a recent $n^{O(\varepsilon^{-2}\log n)}$ algorithm for a problem in quantum information theory, due to Brandao, Christandl, and Yard (for details see Section 4). And second, we wish to show that, assuming the ETH, the “obvious” $\mathsf{AM}\left(2\right)$ protocol for 3Sat is optimal even in the very low-error and high-error cases. The dense CSP results do not get us close to such a statement, but our algorithm does.

More broadly, appealing to the dense CSP literature feels like overkill if we just want to show (for example) that our 3Sat protocol is optimal, or that the values of free games can be approximated in quasipolynomial time. If we can prove those results in an elementary, self-contained way, then it seems like we should—particularly because our proofs might help to make certain striking techniques from the dense CSP world more accessible than they would be otherwise.

Their algorithm also implies that $\mathsf{AM}\left(2\right)\subseteq\mathsf{EXP}$, and that our 3Sat protocol is essentially optimal assuming the ETH. On the other hand, it seems unlikely that their algorithm can be used to get the containment $\mathsf{AM}\left(2\right)\subseteq\mathsf{AM}^{\mathsf{NP}}$, let alone $\mathsf{AM}\left(2\right)=\mathsf{AM}$.

3 Generalizing to k𝑘k Merlins

One might wonder whether our limitation theorems for $\mathsf{AM}\left(2\right)$ protocols could be evaded by simply adding more Merlins. So for example, even if $\mathsf{AM}\left(2\right)$ protocols for 3Sat require $\Omega(\sqrt{n})$ communication (assuming the ETH), could there be an $\mathsf{AM}\left(3\right)$ protocol that used $O(n^{1/3})$ communication, an $\mathsf{AM}\left(10\right)$ protocol that used $O(n^{1/10})$ communication, and so forth? In Sections 7.3 and 7.4, we generalize our limitation theorems to the case of $k$ Merlins, in order to rule out that possibility. In particular, we give the following extensions of our results from Section 3.2:

There is a deterministic algorithm that, given as input a $k$-player free game $G$ with question sets $Y_{1},\ldots,Y_{k}$ and answer sets $B_{1},\ldots,B_{k}$, approximates $\omega\left(G\right)$ to within $\pm\varepsilon$ in time

where $n=\left|Y_{1}\right|\left|B_{1}\right|\cdots\left|Y_{k}\right|\left|B_{k}\right|$ is the input size. (There is also an alternative algorithm that runs in time $n^{\varepsilon^{-O\left(1\right)}\log n}$, independently of $k$.)

$\mathsf{AM}\left(k\right)\subseteq\mathsf{EXP}$ for all $k=\operatorname*{poly}\left(n\right)$. (Indeed, any constant-soundness $\mathsf{AM}\left(k\right)$ protocol involving $p\left(n\right)$ total bits of communication can be simulated in $2^{O(p\left(n\right)^{2})}\operatorname*{poly}\left(n\right)$ randomized time, or $2^{O(p\left(n\right)^{2})}\operatorname*{poly}\left(n\right)$ deterministic time if Arthur’s verification procedure is deterministic.)

Assuming the Randomized ETH, any constant-soundness $\mathsf{AM}\left(k\right)$ protocol for 3Sat must use $\Omega(\sqrt{n})$ total bits of communication, regardless of how large $k$ is. (If, moreover, Arthur’s verification procedure is deterministic, then it suffices to assume the ordinary ETH.)

$\mathsf{AM}\left(k\right)=\mathsf{AM}$ for all $k=\operatorname*{poly}\left(n\right)$.

We first prove (1’), and then derive (2’) and (3’) as consequences. For (1’), the basic idea is to generalize our approximation algorithm for $2$-player free games to $k$-player games, by calling the algorithm recursively to “peel off players one at a time.” In other words, we reduce the approximation of a $k$-player game to the approximation of a quasipolynomial number of $\left(k-1\right)$-player games, and continue recursing until we get down to $1$ player. When we do this, we need to control the buildup of error across all $k$ levels of the recursion, and that is why we get a factor of $k^{2}$ in the exponent of the running time. Later, by using the subsampling machinery, we will be able to go back and give an alternative algorithm whose running time depends only on $n$, not on $k$. And that, in turn, will let us show that assuming the ETH, any $\mathsf{AM}\left(k\right)$ protocol for 3Sat must use $\Omega(\sqrt{n})$ total bits of communication, regardless of $k$. (Our first algorithm only implies a lower bound of $k+\Omega(\sqrt{n}/k)=\Omega(n^{1/4})$ on the total communication, assuming the ETH.) The tradeoff is that the running time of the alternative algorithm depends exponentially on $\varepsilon^{-\Lambda}$ for some large constant $\Lambda$, rather than on $\varepsilon^{-2}$.

For (4’), we need to show that the subsampling theorem of Barak et al. continues to give us what we want, so long as $k=\operatorname*{poly}\left(n\right)$. This boils down to proving a good subsampling theorem for $k$-player free games. That is, given any $k$-player free game $G=\left(Y_{1},\ldots,Y_{k},B_{1},\ldots,B_{k},V\right)$ of total size $n=\left|Y_{1}\right|\left|B_{1}\right|\cdots\left|Y_{k}\right|\left|B_{k}\right|$, we need to show that its value $\omega\left(G\right)$ can be approximated to within additive error $\pm\varepsilon$, by restricting attention to random subsets of questions $\left(S_{i}\subset Y_{i}\right)_{i\in\left[k\right]}$, where each $S_{i}$ has size $\varepsilon^{-O\left(1\right)}\log n$. A direct adaptation of our argument from the $k=2$ case turns out not to work here (it breaks down when $k$ is greater than $O\left(\log n\right)$), but we give an alternative encoding of $k$-player free games by $k$-CSPs that works for all $k=\operatorname*{poly}\left(n\right)$.

Quantum Motivation

In studying $\mathsf{AM}\left(2\right)$, our original motivation was to understand the quantum complexity class $\mathsf{QMA}\left(2\right)$ (i.e., two-prover Quantum Merlin-Arthur). So in this section, we provide some background about $\mathsf{QMA}\left(2\right)$, and explain the tantalizingly close analogy between it and $\mathsf{AM}\left(2\right)$. Readers who don’t care about quantum complexity theory can skip this section.

Recall that “ordinary” $\mathsf{QMA}$ is just the quantum analogue of $\mathsf{MA}$:

$\mathsf{QMA}$ is the class of languages $L\subseteq\left\{0,1\right\}^{\ast}$ for which there exists a polynomial-time quantum algorithm $Q$ such that, for all inputs $x\in\left\{0,1\right\}^{n}$:

If $x\in L$ then there exists a quantum witness state $\left|\phi\right\rangle$, on $\operatorname*{poly}\left(n\right)$ qubits, such that $Q\left(x,\left|\phi\right\rangle\right)$ accepts with probability at least $2/3$.

If $x\notin L$ then $Q\left(x,\left|\phi\right\rangle\right)$ accepts with probability at most $1/3$, for all purported witness states $\left|\phi\right\rangle$.

A lot is known about $\mathsf{QMA}$: for example, it has natural complete promise problems, admits amplification, and is contained in $\mathsf{PP}$ (see Aharonov and Naveh for a survey).

Now, $\mathsf{QMA}\left(k\right)$ (introduced by Kobayashi et al. ) is just like $\mathsf{QMA}$, but with $k$ Merlins who are assumed to be unentangled. Note that, if the Merlins were entangled, then the joint state they sent to Arthur could be arbitrary—so from Arthur’s perspective, there might as well be only one Merlin.For precisely this reason, in the classical case we trivially have $\mathsf{MA}\left(k\right)=\mathsf{MA}$ for all $k=\operatorname*{poly}\left(n\right)$. With $\mathsf{QMA}\left(k\right)$, the hope is that, ironically, Arthur can exploit his knowledge that the messages are unentangled to verify statements that he otherwise could not. More formally:

$\mathsf{QMA}\left(k\right)$ is the class of languages $L\subseteq\left\{0,1\right\}^{\ast}$ for which there exists a polynomial-time quantum algorithm $Q$ such that, for all inputs $x\in\left\{0,1\right\}^{n}$:

If $x\in L$, then there exist quantum witness states $\left|\phi_{1}\right\rangle,\ldots,\left|\phi_{k}\right\rangle$, each on $\operatorname*{poly}\left(n\right)$ qubits, such that $Q\left(x,\left|\phi_{1}\right\rangle\otimes\cdots\otimes\left|\phi_{k}\right\rangle\right)$ accepts with probability at least $2/3$.

If $x\notin L$ then $Q\left(x,\left|\phi_{1}\right\rangle\otimes\cdots\otimes\left|\phi_{k}\right\rangle\right)$ accepts with probability at most $1/3$ for all purported witness states $\left|\phi_{1}\right\rangle,\ldots,\left|\phi_{k}\right\rangle$.

Compared to $\mathsf{QMA}$, strikingly little is known about $\mathsf{QMA}\left(2\right)$. Clearly

but we do not know any better containments. We do not even have strong evidence that $\mathsf{QMA}\left(2\right)\neq\mathsf{QMA}$, or at the other extreme that $\mathsf{QMA}\left(2\right)\neq\mathsf{NEXP}$. Harrow and Montanaro showed that $\mathsf{QMA}\left(2\right)$ allows exponential amplification of success probabilities, and that $\mathsf{QMA}\left(2\right)=\mathsf{QMA}\left(k\right)$ for all $k\geq 3$; even these were surprisingly nontrivial results.

Of course, $\mathsf{QMA}\left(2\right)$ would be of limited interest, if we could never actually exploit the promise of unentanglement to do anything new. In 2007, however, Blier and Tapp gave a $\mathsf{QMA}\left(2\right)$ protocol for the $\mathsf{NP}$-complete 3Coloring problem, using two quantum witnesses with only $\log n$ qubits each. The catch was that Arthur has only a $1/\operatorname*{poly}\left(n\right)$ probability of catching the Merlins if they cheat. Even then, however, any one-prover $\mathsf{QMA}$ protocol with the same parameters would imply $\mathsf{NP}\subseteq\mathsf{BQP}$.

Independently, Aaronson et al. gave a protocol to convince Arthur that a 3Sat instance of size $n$ is satisfiable, using $\widetilde{O}(\sqrt{n})$ quantum witnesses with $\log n$ qubits each. Unlike Blier and Tapp’s protocol, Aaronson et al.’s achieved constant soundness, and that is why it required more communication ($\widetilde{O}(\sqrt{n})$ rather than $\log n$). Shortly afterward, Aaronson et al.’s protocol was improved by Harrow and Montanaro , who showed how to prove 3Sat using two quantum witnesses with $\widetilde{O}(\sqrt{n})$ qubits each; and in a different direction by Chen and Drucker , who showed how to measure each of the $\widetilde{O}(\sqrt{n})$ witnesses separately from the others.It is still not known whether one can combine the Harrow-Montanaro and Chen-Drucker improvements, to get a 3Sat protocol using two witnesses of $\widetilde{O}(\sqrt{n})$ qubits each that are measured separately from each other.

Without going into too much detail, all of these $\widetilde{O}(\sqrt{n})$-qubit protocols for 3Sat ultimately rely on the Birthday Paradox. In particular, they all involve Arthur measuring $k$ quantum registers with $\log n$ qubits each—and if we want constant soundness, then (roughly speaking) we need a constant probability that two or more of Arthur’s measurements will reveal information about the same 3Sat variable $x_{j}$. And that is why we need $k=\Omega(\sqrt{n})$.

It is tempting to speculate that $\sqrt{n}$ qubits represents some sort of fundamental barrier for multi-prover $\mathsf{QMA}$ protocols: i.e., that assuming we want constant soundness, we can save a quadratic factor in the number of qubits needed to prove 3Sat, but no more than that. Certainly it would be astonishing if 3Sat could be proved (with constant soundness) using two unentangled witnesses with only $\operatorname*{polylog}n$ qubits each. In that case, “scaling up” by an exponential, we would presumably get that $\mathsf{QMA}\left(2\right)=\mathsf{NEXP}$.

When one thinks about the above questions—or for that matter, almost any questions about $\mathsf{QMA}\left(2\right)$—one is inevitably led to a computational problem that Harrow and Montanaro called the Best Separable State or BSS problem.

to additive error $\pm\varepsilon$. (Here $\varepsilon$ is assumed to be an arbitrarily small constant if not specified otherwise.)

is just the largest eigenvalue of $A$, which is easy to compute. Indeed, the proof of $\mathsf{QMA}\subseteq\mathsf{PP}$ works by reducing the simulation of a $\mathsf{QMA}$ protocol to the computation of $\lambda\left(A\right)$, for some exponentially-large Hermitian matrix $A$.

By contrast, BSS asks us to maximize $u^{{\dagger}}Au$ only over unit vectors of the form $u=v\otimes w$. That is why BSS models the problem of maximizing the verifier’s acceptance probability in a $\mathsf{QMA}\left(2\right)$ protocol, where the maximum is taken over all separable witnesses, of the form $\left|\phi_{1}\right\rangle\otimes\left|\phi_{2}\right\rangle$. From this standpoint, the reason why $\mathsf{QMA}\left(2\right)$ is so much harder to understand than $\mathsf{QMA}$—but also why $\mathsf{QMA}\left(2\right)$ is potentially more powerful—is that (as one can check) BSS is a non-convex optimization problem, which lacks the clean linear-algebraic structure of computing $\lambda\left(A\right)$.

Indeed, from the protocol of Blier and Tapp mentioned earlier, it follows immediately that we can reduce 3Coloring to the problem of approximating $\lambda_{\operatorname*{sep}}\left(A\right)$ up to additive error $\pm 1/\operatorname*{poly}\left(n\right)$. Furthermore, since the quantum witnesses in the Blier-Tapp protocol have only $\log n$ qubits, the resulting matrix $A$ will have size $2^{O\left(\log n\right)}=\operatorname*{poly}\left(n\right)$. Thus:

BSS${}_{1/\operatorname*{poly}\left(n\right)}$ is $\mathsf{NP}$-hard.

One wants to know: is BSSε still a hard problem even for constant $\varepsilon$? Because it has constant soundness, the protocol of Harrow and Montanaro (building on Aaronson et al. ) lets us reduce 3Sat to the problem of approximating $\lambda_{\operatorname*{sep}}\left(A\right)$ up to constant additive error. Now, since the quantum witnesses in the Harrow-Montanaro protocol have $\widetilde{O}(\sqrt{n})$ qubits, the resulting matrix $A$ has size $2^{\widetilde{O}(\sqrt{n})}$, so we do not get a polynomial-time reduction. We do, however, get something:

If BSS is solvable in $t\left(n\right)$ time, then 3Sat is solvable in $t(2^{\widetilde{O}(\sqrt{n})})$ time. So in particular, assuming the Exponential Time Hypothesis, BSS requires $n^{\Omega\left(\log n\right)}$ deterministic time. (Likewise, assuming the Randomized ETH, BSS requires $n^{\Omega\left(\log n\right)}$ randomized time.)

Could we go further than Theorems 17 and 18, and prove that BSSε is $\mathsf{NP}$-hard even for constant $\varepsilon$? Notice that if we could, then “scaling up by an exponential,” we could presumably also show $\mathsf{QMA}\left(2\right)=\mathsf{NEXP}$! If, on the other hand, we believe (as seems plausible) that $\mathsf{QMA}\left(2\right)\subseteq\mathsf{EXP}$, then we seem forced to believe that BSS is solvable in $n^{\operatorname*{polylog}n}$ time, even if we have no idea what the algorithm is.Strictly speaking, neither of these implications is a theorem. For example, even if BSSε turned out to be $\mathsf{NP}$-hard for constant $\varepsilon$, it’s possible that one could exploit the special structure of the matrices arising from polynomial-size quantum circuits to show that $\mathsf{QMA}\left(2\right)\subseteq\mathsf{EXP}$. In practice, however, a “reasonable” proof that BSSε is $\mathsf{NP}$-hard would probably also imply $\mathsf{QMA}\left(2\right)=\mathsf{NEXP}$, and a “reasonable” proof of $\mathsf{QMA}\left(2\right)\subseteq\mathsf{EXP}$ would probably proceed by solving BSSε in quasipolynomial time.

Raising the stakes even further, Barak et al. showed that BSS is intimately related to other problems of great current interest in complexity theory: namely, the Unique Games, Small Set Expansion, and 2-to-4 Norm problems.We refer the reader to for the definitions of these problems, but very briefly: Unique Games (UG) is the problem of deciding whether $\omega(G)$ is close to $1$ or close to , given as input a description of a two-prover game $G=\left(X,Y,A,B,\mathcal{D},V\right)$ with the special properties that $\left|A\right|=\left|B\right|$, and that for every $\left(x,y\right)\in X\times Y$ there exists a permutation $\pi_{x,y}$ such that $V(x,y,a,b)=1$ if and only if $b=\pi_{x,y}(a)$. Small Set Expansion (SSE) is the problem of deciding whether a given graph $G$ is close to or far from an expander graph, if we consider $G$’s expansion on “small” subsets of vertices only. 2-to-4 Norm (2-to-4) is the problem, given as input an $n\times n$ matrix $A$, of approximating the maximum of $\left\|Av\right\|_{4}$ over all vectors $v$ such that $\left\|v\right\|_{2}=1$. The lattice of known reductions among these problems is as follows:

Now, assuming the ETH, Theorem 18 gives us $n^{\Omega\left(\log n\right)}$ hardness for BSS—and as a direct consequence, for 2-to-4 Norm as well. That might not sound like much, but it’s a lot more than we currently know for either Unique Games or Small Set Expansion! So the speculation arises that, if we fully understood BSS, we might be able to apply some of the insights to UG or SSE.

To lay our cards on the table, here is our conjecture about BSS:

BSSε is solvable in deterministic $n^{O(\varepsilon^{-2}\log n)}$ time.

If true, Conjecture 19 readily implies that $\mathsf{QMA}\left(2\right)\subseteq\mathsf{EXP}$. Since a $t\left(n\right)$-time algorithm for BSS can be combined with a $q\left(n\right)$-qubit $\mathsf{QMA}\left(2\right)$ protocol for 3Sat to get a $t(2^{O\left(q\left(n\right)\right)})$-time algorithm for 3Sat, Conjecture 19 also implies that, assuming the ETH, any $\mathsf{QMA}\left(2\right)$ protocol for 3Sat must use $\Omega(\sqrt{n})$ qubits.

There has been some progress toward a proof of Conjecture 19. In particular, Brandao, Christandl, and Yard gave an algorithm that solves BSSε in $n^{O(\varepsilon^{-2}\log n)}$ time if $\left\|A\right\|_{2}=O\left(1\right)$, or alternatively, if $A$ represents a quantum measurement that can be implemented using LOCC (Local Operations and Classical Communication). This implied, among other things, that $\mathsf{QMA}_{\mathsf{LOCC}}\left(k\right)=\mathsf{QMA}$ for $k=O\left(1\right)$, where $\mathsf{QMA}_{\mathsf{LOCC}}\left(k\right)$ is the subclass of $\mathsf{QMA}\left(k\right)$ in which Arthur is restricted to LOCC measurements. Brandao et al.’s algorithm uses a technique that quantum information researchers know as symmetric extension, and that theoretical computer scientists know as the Lasserre hierarchy. It is not known whether similar techniques could work for arbitrary $\mathsf{QMA}\left(k\right)$ protocols.

More recently, Brandao and Harrow showed that, assuming the ETH, any so-called $\mathsf{BellQMA}\left(k\right)$ protocol for 3Sat—that is, any $\mathsf{QMA}\left(k\right)$ protocol where each of the $k$ witnesses are measured separately—must use $n^{1/2-o\left(1\right)}$ qubits. This lower bound is known to be essentially tight, due to the protocol of Chen and Drucker . The requirement that each witness be measured separately (with the measurement outcomes then combined with classical postprocessing) is even more stringent than the requirement of LOCC. Despite this, the result of Brandao and Harrow did not follow from the earlier result of Brandao, Christandl, and Yard that $\mathsf{QMA}_{\mathsf{LOCC}}\left(k\right)=\mathsf{QMA}$, because the latter works only for constant $k$.

But what does any of the above have to do with $\mathsf{AM}\left(2\right)$? One way to view this paper’s contribution is as follows: we prove that a “classical analogue” of Conjecture 19 holds. In more detail, we can think of $\mathsf{AM}\left(2\right)$ as closely analogous in many ways to $\mathsf{QMA}\left(2\right)$. For both classes, the only obvious lower bound comes from restricting to a single Merlin, while the only obvious upper bound is $\mathsf{NEXP}$. For both classes, the difficulty with proving an $\mathsf{EXP}$ upper bound is the requirement that the Merlins can’t communicate, which gives rise to a non-convex optimization problem. For both classes, there exists a protocol for 3Sat that uses $\log n$ communication, but that has only a $1/\operatorname*{poly}\left(n\right)$ probability of catching cheating Merlins. For both classes, we can improve the 3Sat protocol to have constant soundness, by using a strong PCP theorem together with the Birthday Paradox—but if we do so, then the communication cost increases from $\log n$ to $\widetilde{O}(\sqrt{n})$.

Because the analogy runs so deep, it seems of interest to $\mathsf{QMA}\left(2\right)$ researchers to know that:

FreeGameε is solvable in $n^{O(\varepsilon^{-2}\log n)}$ time, as we conjecture that BSSε is.

$\mathsf{AM}\left(2\right)$ is contained in $\mathsf{EXP}$, as we conjecture that $\mathsf{QMA}\left(2\right)$ is.

The $\widetilde{O}(\sqrt{n})$-communication $\mathsf{AM}\left(2\right)$ protocol for 3Sat is essentially optimal assuming the ETH, as we conjecture that the corresponding $\mathsf{QMA}\left(2\right)$ protocol is.

Of course, we also show in this paper that $\mathsf{AM}\left(2\right)=\mathsf{AM}$. So pushing the analogy between $\mathsf{AM}\left(2\right)$ and $\mathsf{QMA}\left(2\right)$ all the way to the end would lead to the conjecture that $\mathsf{QMA}\left(2\right)=\mathsf{QMA}$. We remain agnostic about whether the analogy extends that far!

Preliminaries

Some notation: we use $\operatorname{E}$ for expectation, $\left[n\right]$ for $\left\{1,\ldots,n\right\}$, and $\binom{\left[n\right]}{k}$ for the set of subsets of $\left[n\right]$ of size $k$. In addition to the notation $\widetilde{O}(f\left(n\right))$ for $O(f\left(n\right)\operatorname*{polylog}f\left(n\right))$, we also use $\widetilde{\Omega}(f\left(n\right))$ for $\Omega(f\left(n\right)/\operatorname*{polylog}f\left(n\right))$. All logs are base $2$ unless specified otherwise.

Sections 1 and 2 have already defined many of the concepts we will need, including two-prover games, free games, the clause/variable game, the birthday repetition, and the FreeGame problem. For completeness, though, we now give the general definition of $k$-player free games.

finite question sets $Y_{1},\ldots,Y_{k}$ and answer sets $B_{1},\ldots,B_{k}$, and

a verification function $V:Y_{1}\times\cdots\times Y_{k}\times B_{1}\times\cdots\times B_{k}\rightarrow\left[0,1\right]$.

The value of the game, denoted $\omega\left(G\right)$, is the maximum, over all tuples of response functions $\left(b_{i}:Y_{i}\rightarrow B_{i}\right)_{i\in\left[k\right]}$ , of

Directly related to $k$-player free games is the complexity class $\mathsf{AM}\left(k\right)$, which we now formally define.$\mathsf{AM}\left(k\right)$ should not be confused with $\mathsf{AM}\left[k\right]$, which means $\mathsf{AM}$ with a single Merlin but $k$ rounds of communication. A classic result of Babai and Moran says that $\mathsf{AM}\left[k\right]=\mathsf{AM}\left[2\right]=\mathsf{AM}$ for all constants $k\geq 2$. When $k=\operatorname*{poly}\left(n\right)$, by contrast, such a collapse is not believed to happen, since $\mathsf{AM}\left[\operatorname*{poly}\right]=\mathsf{IP}=\mathsf{PSPACE}$.

Let $k$ be a positive integer. Then $\mathsf{AM}\left(k\right)$ is the class of languages $L\subseteq\left\{0,1\right\}^{\ast}$ for which there exists a probabilistic polynomial-time verifier $V$ such that for all $n$ and all inputs $x\in\left\{0,1\right\}^{n}$:

(Completeness) If $x\in L$, then there exist functions $b_{1},\ldots,b_{k}:\left\{0,1\right\}^{\operatorname*{poly}\left(n\right)}\rightarrow\left\{0,1\right\}^{\operatorname*{poly}\left(n\right)}$, depending on $x$, such that

(Soundness) If $x\notin L$, then for all such functions $b_{1},\ldots,b_{k}$,

Clearly $\mathsf{AM}\left(1\right)=\mathsf{AM}$ and $\mathsf{AM}\left(k\right)\subseteq\mathsf{AM}\left(k+1\right)$ for all $k$. We also have $\mathsf{AM}\left(k\right)\subseteq\mathsf{MIP}\left(k\right)$, thereby giving the crude upper bound $\mathsf{AM}\left(k\right)\subseteq\mathsf{NEXP}$ (later we will do much better).

We can easily generalize the definition of $\mathsf{AM}\left(k\right)$ to $\mathsf{AM}\left(k\left(n\right)\right)$, for any growth rate $k\left(n\right)=O\left(\operatorname*{poly}\left(n\right)\right)$. Also, let $\mathsf{AM}_{p\left(n\right)}\left(k\right)$ be the variant of $\mathsf{AM}\left(k\right)$ where all messages (both the $y_{i}$’s and the $b_{i}$’s) are constrained to be $p\left(n\right)$ bits long.

Given any probabilistic complexity class $\mathcal{C}$, one of the first questions we can ask is whether $\mathcal{C}$ admits amplification of success probabilities—or equivalently, whether $\mathcal{C}$ is robust under changing its error parameters (such as $1/3$ and $2/3$). At least for $\mathsf{AM}\left(2\right)$, we are fortunate that a positive answer follows from known results. In particular, building on the Parallel Repetition Theorem (Theorem 12), Rao proved a useful concentration bound for the parallel repetitions of two-prover games:

For all $\delta>0$ and all two-prover games $G=\left(X,Y,A,B,\mathcal{D},V\right)$, if Merlin1 and Merlin2 play the parallel repeated version $G^{N}$, then they can win more than a $\omega\left(G\right)+\delta$ fraction of the games with probability at most

Theorem 22 implies that “amplification works” for $\mathsf{AM}\left(2\right)$ protocols:

In the definition of $\mathsf{AM}\left(2\right)$, replacing the constants $\left(1/3,2/3\right)$ by $\left(a,b\right)$ for any constants $0<a<b<1$, or indeed by $\left(2^{-p\left(n\right)},1-2^{-p\left(n\right)}\right)$ or $\left(1/2-1/p\left(n\right),1/2+1/p\left(n\right)\right)$ for any polynomial $p$, gives rise to the same complexity class.

Proof. Suppose, for example, that we want to amplify $\left(1/3,2/3\right)$ to $\left(2^{-p\left(n\right)},1-2^{-p\left(n\right)}\right)$; the other cases are analogous. Given a language $L\in\mathsf{AM}\left(2\right)$ and an input $x\in\left\{0,1\right\}^{n}$, the $\mathsf{AM}\left(2\right)$ protocol for checking whether $x\in L$ can be represented as a free game $G=\left(X,Y,A,B,V\right)$, where $X=Y=A=B=\left\{0,1\right\}^{q\left(n\right)}$ for some polynomial $q$. We have $\omega\left(G\right)\geq 2/3$ if $x\in L$, and $\omega\left(G\right)\leq 1/3$ if $x\notin L$. Now let $G_{1/2}^{N}$ be the game where the Merlins play $N$ parallel instances of the original game $G$, and they “win” if and only if they win on at least $N/2$ instances. If $\omega\left(G\right)\geq 2/3$, then clearly $\omega(G_{1/2}^{N})\geq 1-2^{-\Omega\left(N\right)}$—since if the Merlins just play their optimal strategy for $G$ on each of the $N$ instances separately, then the number that they win will be concentrated around $\omega\left(G\right)N\geq 2N/3$ by a standard Chernoff bound. On the other hand, if $\omega\left(G\right)\leq 1/3$, then Theorem 22 implies that $\omega(G_{1/2}^{N})\leq 2^{-\Omega\left(N/q\left(n\right)\right)}$. So, by simply choosing $N\gg p\left(n\right)q\left(n\right)$ to be a suitably large polynomial, we can ensure that $\omega(G_{1/2}^{N})\geq 1-2^{-p\left(n\right)}$ if $x\in L$ while $\omega(G_{1/2}^{N})\leq 2^{-p\left(n\right)}$ if $x\notin L$.

Note that Proposition 23 can blow up the communication cost by a polynomial factor, because of the dependence of $N$ on $q\left(n\right)$ (which derives from the $1/\log\left|A\right|\left|B\right|$ factor in the exponent from Theorem 22). For this reason, Proposition 23 doesn’t directly imply any useful amplification for our $\widetilde{O}(\sqrt{n})$-communication protocol for 3Sat. See Section 6.3 for further discussion of this issue, and for our best current results for the low-error case.

Rao (personal communication) believes that it would be straightforward to generalize Theorem 22 to games with $k\geq 3$ players, as long as the games are free.By contrast, for general games with $k\geq 3$ players, even proving a “standard” parallel repetition theorem is a notorious open problem. If so, then we would also obtain an amplification theorem for $\mathsf{AM}\left(k\right)$, for all $k=\operatorname*{poly}\left(n\right)$. However, this generalization has not yet been worked out explicitly.

One last remark: a classic result about “ordinary” $\mathsf{AM}$ (see ) states that any $\mathsf{AM}$ protocol can be made to have perfect completeness. In other words, the condition $x\in L\Rightarrow\Pr\left[V\text{ accepts}\right]\geq 2/3$ can be strengthened to $x\in L\Rightarrow\Pr\left[V\text{ accepts}\right]=1$ without loss of generality. Another classic result states that any $\mathsf{AM}$ protocol can be made public-coin, meaning that any random bits generated by Arthur are immediately shared with Merlin. In terms of games, the public-coin property would imply in particular that Arthur’s verification function was deterministic: that is, $V\left(x,y,a,b\right)\in\left\{0,1\right\}$ for all $x,y,a,b$.

Thus, one might wonder whether any $\mathsf{AM}\left(k\right)$ protocol can be made perfect-completeness and public-coin as well. Ultimately, affirmative answers to these questions will follow from our result that $\mathsf{AM}\left(k\right)=\mathsf{AM}$, which works regardless of whether the original $\mathsf{AM}\left(k\right)$ protocol had perfect completeness or was public-coin. But it would be interesting to find direct proofs of these properties for $\mathsf{AM}\left(k\right)$. (It would also be interesting to find a direct proof that $\mathsf{AM}\left(k\right)=\mathsf{AM}\left(2\right)$ for all $k>2$, rather than deducing this as a consequence of $\mathsf{AM}\left(k\right)=\mathsf{AM}$.)