PaperlayerView exact revision on arXiv

Source-linked AI summary

AM with Multiple Merlins

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

arXiv:1401.6848v1cs.CCquant-ph

TL;DR

The paper asks what power independent-question multiple-prover protocols add and how hard free-game approximation is. It develops free-game algorithms, subsampling results, and a 3Sat protocol, establishing both quasipolynomial approximation and ETH-based hardness, while showing AM(k)=AM for polynomial k.

  • Problem

    The paper asks how AM(2) compares with single-prover AM and MIP, and how difficult it is to approximate explicit free-game values.

    Source: §1.1 · p. 4

  • Method

    It studies independent-question free games, constructs a 3Sat reduction and protocol, and uses subsampling results to relate free-game values to smaller random subgames.

    Source: §1.1 · p. 4, §2.2 · p. 5, §7 · p. 28

  • Results

    Free games admit quasipolynomial-time approximation and ETH-based hardness, while AM(k)=AM for polynomial k.

    Source: §7 · p. 28, §8 · p. 44

  • Takeaways & Limitations

    The results place free games between quasipolynomial-time approximation and ETH-based hardness, despite their independent questions.

    Source: §8 · p. 44

    The initial low-error approach cannot establish the ETH lower bound for small ε because parallel repetition incurs a necessary 1/log|A||B| exponent factor.

    Source: §6.1 · p. 22, §6.3 · p. 25

Abstract

from arXiv · show

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close analogies between it and the quantum complexity class QMA(k), but the AM(k) model is also natural in its own right. We illustrate the power of multiple Merlins by giving an AM(2) protocol for 3SAT, in which the Merlins' challenges and responses consist of only n^{1/2+o(1)} bits each. Our protocol has the consequence that, assuming the Exponential Time Hypothesis (ETH), any algorithm for approximating a dense CSP with a polynomial-size alphabet must take n^{(log n)^{1-o(1)}} time. Algorithms nearly matching this lower bound are known, but their running times had never been previously explained. Brandao and Harrow have also recently used our 3SAT protocol to show quasipolynomial hardness for approximating the values of certain entangled games. In the other direction, we give a simple quasipolynomial-time approximation algorithm for free games, and use it to prove that, assuming the ETH, our 3SAT protocol is essentially optimal. More generally, we show that multiple Merlins never provide more than a polynomial advantage over one: that is, AM(k)=AM for all k=poly(n). The key to this result is a subsampling theorem for free games, which follows from powerful results by Alon et al. and Barak et al. on subsampling dense CSPs, and which says that the value of any free game can be closely approximated by the value of a logarithmic-sized random subgame.

1 Introduction

The introduction frames two-prover games as a foundation for complexity and approximation hardness, then asks what changes when Arthur's questions are independent. It defines AM(2) through free games and identifies both its power and the complexity of approximating their values as open questions.

1 Introduction

  • The PCP characterization of NP and the theorem MIP = NEXP can both be viewed through the difficulty of estimating two-prover game values.Hardness for these games also feeds into hardness results for constraint-satisfaction problems and other combinatorial optimization problems.Source: §1 · pp. 2–3
  • Two-prover games use question sets, answer sets, a question-pair distribution, and a verification function; their value is the maximum expected verification score over response strategies.The provers agree on strategies beforehand but cannot communicate during play.Source: §1 · p. 2
  • Explicit reductions describe the game and verifier in polynomial time, whereas implicit reductions use polynomial-time sampling and verification; PCP and MIP correspond to these representations, respectively.The paper notes the associated pattern PCP = NP and MIP = NEXP.Source: §1 · p. 3

1.1 Restricting to Independent Questions

  • A free game uses independent, uniformly random questions, and this restriction connects two-prover games to dense constraint-satisfaction instances.The paper presents direct study of free-game approximation as a problem that had not received explicit attention.Source: §1.1 · pp. 3–4
  • AM(2) consists of languages implicitly reducible to free-game value approximation, with Arthur sending independent uniformly random challenges to two Merlins.The paper asks whether AM(2) exceeds single-prover AM, how it compares with MIP, and how difficult explicit free-game approximation is.Source: §1.1 · p. 4
  • The study also draws motivation from analogous questions about QMA(2), where the paper suggests the classical model may clarify some of them.The quantum motivation is discussed further in Section 4.Source: §1.1 · p. 4

2 Our Results

The paper establishes quasipolynomial-time approximation and ETH-based hardness for free games, alongside an AM(2) protocol for 3Sat. It also proves that polynomially many Merlins do not increase AM's power.

2 Our Results

  • The paper gives almost matching upper and lower bounds for approximating free-game values, assuming ETH.It also reports hardness for approximating values of certain entangled games, established by Brandao and Harrow [15] using this work's hardness result.Source: §2 · p. 4, §2.2 · p. 6

2.1 Upper Bounds

  • FreeGameε is solvable deterministically in time nO(ε−2 log n), providing a quasipolynomial-time approximation algorithm.The related algorithm of Brandao and Harrow [15] uses linear programming relaxation, while this paper's algorithm is combinatorial.Source: §2.1 · pp. 4–5
  • AM(2) = AM, and the result generalizes to AM(k) = AM for every polynomial number of Merlins.The paper attributes the extra power of multiple provers in this setting to correlated queries, which independent challenges do not provide.Source: §2.1 · p. 5

2.2 Hardness Results

  • The 3Sat reduction yields a free-game instance of size 2 eO(√n) and a protocol with eO(√n)-bit responses, perfect completeness, and a fixed constant soundness gap.The reduction runs in time 2 eO(√n), with eO hiding polylogarithmic factors.Source: §2.2 · p. 5
  • The free-game approximation hardness also yields a variety of hardness results across versions and parameter ranges through different PCP constructions.The reduction from 3Sat to FreeGameε provides the paper's nontrivial AM(2) protocol.Source: §2.2 · pp. 5–6
  • Under ETH, constant-error approximation of dense k-CSPs with polynomial-size alphabets is hard, nearly matching the quasipolynomial upper bound of Barak et al..The paper says this explains why the earlier approximation algorithm was quasipolynomial rather than polynomial-time.Source: §2.2 · p. 6

3 Detailed Overview of Results

The overview presents a birthday-repetition AM(2) protocol for 3Sat, approximation algorithms for free games, and extensions to polynomially many Merlins. These results yield an AM(k)=AM collapse and ETH-based limits on protocol communication.

3.1 3Sat Protocol

  • For the clause/variable game, birthday repetition with k, ℓ = Ω(√n) gives a free game with soundness at most 1−Ω(1).The repetition removes the need for correlated question distributions; its soundness analysis addresses strategies in which each Merlin sees the full list of questions.Source: §3.1 · pp. 7–8
  • The birthday-repetition soundness argument relies on the clause/variable game's uniform constraint graph and is not established for arbitrary games.The authors leave the broader power of birthday repetition for future work.Source: §3.1 · p. 8

3.2 Approximation Algorithms for Free Games

  • FreeGameε has a deterministic n^O(ε^-2 log n)-time approximation algorithm; a randomized algorithm also runs in |X|·|A|^O(ε^-2 log|Y||B|) time.The deterministic bound is also written as (|X||A|)^O(ε^-2 log|Y||B|).Source: §3.2 · p. 8
  • A constant-soundness AM(2) protocol using p(n) communication bits can be simulated in 2^O(p(n)^2) poly(n) time, placing AM(2) in EXP.The simulation is deterministic when Arthur's verification is deterministic and probabilistic otherwise.Source: §3.2 · p. 9
  • Under the ETH, the free-game approximation algorithm makes the paper's 3Sat protocol essentially optimal.The overview's argument is that a protocol with o(√n) communication would permit a 2^o(n)-time decision algorithm for 3Sat.Source: §3.2 · p. 9
  • A logarithmic-sized random subgame approximates any free game's value, yielding AM(k)=AM for polynomially many Merlins.The argument encodes free games as dense CSPs and applies subsampling results.Source: §3.2 · pp. 9–10

3.3 Generalizing to k Merlins

  • Assuming the Randomized ETH, constant-soundness AM(k) protocols for 3Sat require Ω(√n) total communication bits regardless of k.For deterministic verification, the ordinary ETH suffices.Source: §3.3 · p. 11
  • For k-player free games, a recursive approximation algorithm peels off players one at a time, with error accumulation producing a k^2 factor in its running-time exponent.An alternative algorithm has running time n^ε^-O(1) log n independent of k, but has worse dependence on ε.Source: §3.3 · p. 11

4 Quantum Motivation

The paper's motivation comes from parallels between AM(2) and QMA(2), whose unentangled witnesses make the verifier's optimization non-convex. It relates its classical results to open questions about QMA(2), while explicitly leaving the analogy's ultimate extent unresolved.

4 Quantum Motivation

  • BSS models QMA(2) acceptance by maximizing the verifier's acceptance probability over separable witnesses, a non-convex optimization lacking the linear-algebraic structure of the largest-eigenvalue problem.The restriction is to product vectors u = v⊗w.Source: §4 · p. 13
  • Assuming ETH, solving BSS in t(n) time would solve 3Sat in t(2^eO(√n)) time, implying n^Ω(log n) deterministic-time hardness for BSS.The passage also states the corresponding randomized-time lower bound under the Randomized ETH.Source: §4 · p. 14
  • The BSS-to-QMA(2) implications are not theorems: matrices arising from polynomial-size quantum circuits might have special structure that enables different algorithms.The authors describe these implications as plausible reasoning rather than established results.Source: §4 · p. 14

4.1 Connection to Our Results

  • The authors frame their AM(2) results as a classical analogue of conjectured QMA(2) properties, including quasipolynomial-time approximation and containment in EXP.They also relate the ETH-based optimality of the AM(2) 3Sat protocol to a conjectured lower bound for its QMA(2) counterpart.Source: §4.1 · p. 15
  • The authors prove AM(2)=AM but remain agnostic about whether the analogy extends to QMA(2)=QMA.They identify the no-communication constraint as a source of non-convex optimization in both settings.Source: §4.1 · p. 15

5 Preliminaries

The preliminaries define free games and AM(k), then establish error amplification for AM(2) and distinguish multiple Merlins from multiple rounds. They also preview the result that AM(k) collapses to AM.

5 Preliminaries

  • A k-player free game has finite question and answer sets, a verification function, and value equal to the maximum expected acceptance over response functions.The expectation is over independently drawn questions from the players' question sets.Source: §5 · p. 16
  • AM(k) uses k non-communicating Merlins who receive independent random challenges and respond through separate functions; AM(1)=AM and AM(k)⊆AM(k+1).The class is also contained in MIP(k), giving the stated crude upper bound AM(k)⊆NEXP.Source: §5 · p. 16
  • AM(k) denotes k Merlins, not AM[k], which denotes one Merlin with k communication rounds; for polynomial k, AM[poly]=IP=PSPACE.The cited classic result gives AM[k]=AM[2]=AM for constant k≥2.Source: §5 · p. 16
  • For AM(2), changing completeness and soundness to any fixed gap or to specified inverse-exponential or inverse-polynomial gaps preserves the same complexity class.The stated error pairs include (2^-p(n), 1−2^-p(n)) and (1/2−1/p(n), 1/2+1/p(n)).Source: §5 · p. 17
  • The amplification result can increase communication by a polynomial factor, so it does not directly give useful amplification for the paper's eO(√n)-communication 3Sat protocol.The text attributes this cost to the dependence of the repetition count on the answer length.Source: §5 · p. 17
  • The overview previews that AM(k)=AM regardless of whether the original protocol has perfect completeness or is public-coin.The passage notes that direct proofs of these properties for AM(k) would still be interesting.Source: §5 · p. 18

6 Analysis of the Birthday Game

This section analyzes the birthday game to develop AM(2) protocols for 3SAT with near-square-root communication, moving from constant soundness gaps to low error. It also examines ETH-based limits for distinguishing free-game values and derives a nondeterministic-time containment and relativization caveats.

6 Analysis of the Birthday Game

  • The section announces that NTIME[n] ⊆ AM_n^{1/2+o(1)}(2), and that this implication is nonrelativizing.Source: §6 · p. 18

6.1 The Basic Result

  • A birthday-repetition protocol based on Dinur’s PCP gives 3SAT an AM(2) protocol using eO(√n) communication with a 1 vs. 1−ε gap for constant ε > 0.The proof uses the clause/variable game and bounds the birthday-repeated game’s value when the original formula is unsatisfiable.Source: §6.1 · pp. 21–22
  • Assuming ETH, FreeGame_ε requires n^{eΩ(log n)} time for all sufficiently small constant ε, as implied by the basic protocol’s reduction.The reduction produces a free game whose value is 1 for satisfiable inputs and at most 1−ε for unsatisfiable inputs.Source: §6.1 · p. 22

6.2 The High-Error Case

  • For every ε > 0, 3SAT has an AM(2) protocol using O(√(εn) polylog n) bits with a 1 vs. 1−ε completeness/soundness gap.The section also proves that, assuming ETH, FreeGame_ε requires n^{eΩ(ε^-1 log n)} deterministic time for ε ∈ [1/n, ∆]. The authors conjecture the lower bound could improve to n^{eΩ(ε^-2 log n)} for games with value near 1/2.Source: §6.2 · pp. 24–25

6.3 The Low-Error Case

  • Ordinary parallel repetition fails to yield the desired low-error hardness because its exponent’s 1/log |A||B| factor prevents an ETH contradiction.Repeating the clause/variable game before birthday repetition also enlarges its question sets too much for the intended collision argument.Source: §6.3 · pp. 25–26
  • The clause/variable game is a projection game, but its birthday repetition is not; Shaltiel’s free-game construction has answer sets exp((t log |X||Y||A||B|)^C), for some large constant C, preventing the desired ETH contradiction.For the low-error case, the text proposes starting with a PCP that already has low error and ensuring birthday repetition does not increase it much; it identifies Moshkovitz and Raz as the starting point.Source: §6.3 · pp. 25–26
  • n^1/2+o(1) poly(1/δ) communication suffices for an AM(2) protocol for 3Sat with a 1 vs. δ completeness/soundness gap.The protocol applies for all δ > 0.Source: §6.3 · p. 27
  • Under ETH, distinguishing free games with ω(G) = 1 from ω(G) < δ requires n^poly(δ)·(log n)^(1−o(1)) time for deterministic algorithms.The same lower bound holds for randomized algorithms assuming the Randomized ETH.Source: §6.3 · p. 27
  • The authors conjecture this free-game distinction requires n^poly(δ)·(log n)^(1−o(1)) time for all δ ≤ 1/2, matching an upper bound from Theorem 40.They identify improving the alphabet bound in Theorem 33 and refining the birthday-repetition analysis to remove the dependence of k on 1/δ as needed steps.Source: §6.3 · p. 27

6.4 Complexity Consequences

  • NTIME[n] is contained in AM(2) protocols using n^1/2+o(1) communication, with a 2/3 vs. 1/3 completeness/soundness gap.The containment follows by setting δ := 1/3 and combining Theorem 34 with a tight Cook-Levin reduction.Source: §6.4 · p. 28
  • The containment is non-relativizing: there exists an oracle A for which NTIME^A[n] is not contained in AM^A.The proof sketch defines a unary language based on whether an oracle-encoded Boolean function has a 1-input, then uses diagonalization.Source: §6.4 · p. 28
  • Whether the containment is algebrizing in the sense of Aaronson and Wigderson remains open.Source: §6.4 · p. 28

7 Limitations of Multi-Prover AM

This section develops approximation and subsampling methods for free games to analyze the power and limitations of multi-prover AM. It uses random subgames to derive bounds on AM(k) and related ETH-based consequences for approximation and communication.

7.1 The Basic Approximation Algorithm

  • If an AM(2) 3Sat protocol uses o(√n) communication, the stated implication gives a 2^o(n)-time 3Sat algorithm, motivating the section's ETH-based optimality goal.Source: §7 · p. 28
  • A randomized algorithm estimates a free game's value within ±ε with at least 2/3 success probability in |X| · |A|^O(ε^-2 log|Y||B|) time.A deterministic algorithm achieves the same additive error in (|X||A|)^O(ε^-2 log|Y||B|) time.Source: §7.1 · p. 29
  • A deterministic n^O(ε^-1 log n)-time algorithm distinguishes ω(G) = 1 from ω(G) ≤ 1 − ε under the stated promise; the section also gives AM(2) ⊆ EXP and AM(2) ⊆ AMNP.Source: §7.1 · pp. 30–32

7.2 Subsampling for Free Games and AM (2) = AM

  • For κ = 2ε^-Λ log(|A| + |B|), the expected value of a uniformly random restricted free game lies between ω(G) and ω(G) + ε.The argument encodes the free game as a dense 2-CSP and applies the dense-CSP subsampling result of Barak et al..Source: §7.2 · pp. 33–35
  • AM(2) = AM, using subsampling to simulate a two-Merlin protocol with one Merlin.Arthur samples question sets for both Merlins, sends them to the single Merlin, and checks the replies; the proof bounds completeness and soundness errors and allows amplification.Source: §7.2 · pp. 35–36

7.3 The k-Merlin Case

  • For k-player free games, a deterministic algorithm approximates the game value to additive error ±ε, using a recursive procedure that fixes Merlins one at a time.The procedure reduces estimation to smaller games with one fewer Merlin, continuing recursively until a single-player game can be handled by maximization.Source: §7.3 · p. 36
  • AM(k) ⊆ EXP for every polynomial k, by representing the protocol as a free game and estimating its value to distinguish acceptance from rejection.The proof uses a constant additive-error estimate and evaluates Arthur’s verification function deterministically, with exponential time in its randomness length.Source: §7.3 · pp. 39–40
  • Assuming ETH, constant-soundness AM(k) protocols for 3Sat need Ω(n^1/4) communication regardless of k; when k = n^o(1), they need n^1/2−o(1).Under Randomized ETH, a 1 versus 1−ε gap requires Ω((εn)^1/4) total communication; deterministic verification allows ordinary ETH for that bound.Source: §7.3 · p. 40

7.4 Subsampling with k Merlins

  • The k-Merlin subsampling extension begins by generalizing the two-player theorem, reducing free games to k-CSPs differently because of the theorem’s denseness definition.This passage sets up the extension but does not state its resulting theorem.Source: §7.4 · p. 40
  • Sampling κ = ε^-Λ log(|B1| ··· |Bk|) questions per Merlin gives a random subgame whose value supports approximation of the original free-game value.The construction encodes each k-tuple of questions as a variable and uses a constraint for every k-variable subset, giving a dense CSP with alphabet size |B1| ··· |Bk|.Source: §7.4 · pp. 40–42
  • AM(k) = AM for all k = poly(n), by simulating the multiple-Merlin protocol using sampled question sets and estimating its success probability.Arthur sends each Merlin’s sampled questions, receives a strategy for each set, then estimates the subsampled success probability.Source: §7.4 · pp. 42–43
  • An additive-ε approximation to a k-player free game’s value takes time n^{ε^-O(1) log n}, where n = |Y1||B1| ··· |Yk||Bk|.The deterministic algorithm enumerates sampled subgames and their strategy tuples.Source: §7.4 · p. 43
  • Assuming Randomized ETH, any constant-gap AM(k) protocol for 3SAT requires Ω(√n) total communication; ordinary ETH suffices when Arthur’s verifier is deterministic.The argument uses the free-game approximation algorithm to decide 3SAT in subexponential time if communication were smaller.Source: §7.4 · p. 43

8 Conclusions and Open Problems

The conclusion recaps the free-game approximation and hardness results, then frames open questions about tightening bounds and extending the methods.

8 Conclusions and Open Problems

  • Free games admit a quasipolynomial-time approximation, while ETH-based hardness leaves them out of reach for polynomial-time algorithms; the paper also proves AM(2) = AM.The authors describe the upper and lower bounds as nearly matching.Source: §8 · p. 44
  • Can the 3Sat protocol improve from NTIME[n] ⊆ AM_n^(1/2+o(1))(2) to communication around exp(O(√n)) using stronger PCP constructions?The proposed route would combine n polylog n size with a 1 vs. δ gap.Source: §8 · p. 44
  • For k ≥ 3, can the two free-game algorithms yield a best-of-both-worlds runtime n^O(ε^-2 log n), implying an Ω(√εn) communication lower bound for AM(k) protocols for 3Sat?The compared algorithms use recursive reduction to (k−1)-player games or subsampling.Source: §8 · p. 44
  • Open questions ask whether birthday repetition keeps reducing cheating probability beyond kℓ = N, and when arbitrary two-prover games permit repetition up to the stated limits.The authors also ask whether an alternative AM(k) protocol can achieve a 1 vs. δ gap with n^(1/2+o(1)) polylog(1/δ) communication.Source: §8 · pp. 44–45
  • The authors ask whether the ETH-based FreeGameε upper and lower bounds can be closed, whether the ε dependence is optimal, and whether PCP verification can avoid birthday-game communication overhead.They conjecture the upper bound is tight, but say existing PCP and parallel-repetition machinery seems insufficient to prove it.Source: §8 · p. 44
  • Further questions concern k-player parallel repetition, direct proofs of AM(k) = AM(2), public-coin perfect completeness, and whether the 3Sat protocol is non-algebrizing.The paper notes that the protocol result is non-relativizing.Source: §8 · p. 45
  • The authors ask how projection or unique-game restrictions affect approximation and hardness, whether entangled Merlins break the 3Sat protocol, and what can be said about QMA(2).They also ask whether AM* protocols with uncorrelated questions make upper bounds for entangled-prover classes more tractable.Source: §8 · p. 45
  • The paper conjectures birthday repetition could give n^e^(Ω(ε^-1 log n)) hardness for approximate Nash equilibrium under ETH, addressing an open problem raised by Hazan and Krauthgamer.The cited prior work assumes planted-clique hardness for its n^Ω(log n) result.Source: §8 · p. 45
Loading 1401.6848v1…