{"id":"09a1316f-e168-4bd4-bbe1-bea8430f2ede","arxiv_id":"2505.05253","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Independent set games with a constant number of questions are RE-complete for entangled provers, so their gapped quantum value is undecidable while the classical problem is polynomial-time solvable.","lead":"This paper proves that a natural family of graph games, called independent set games, has an undecidable promise problem for entangled quantum players, even though the classical version is easy. It supplies a new reduction framework and a stability theorem that may be reused in other quantum complexity results.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Soundness of Theorem A inherits the fourth-root conversion in Theorem 2.4 [MdlS23]; if that external exponent or constant is wrong, the constant gap in Corollary B would not follow.","rationale":"The paper's internal construction is largely sound: The stability theorem (Theorem C) is plausible, and the proof of Lemma 5.1 can be repaired by noting that the smallness of the losing probability δ forces, for each question q, the quantity ε_q = ||Σ_{i,a} P(q,a)_i - 1||_2 to be at most O(ε), so Theorem C applies pointwise. The remaining potential weakness is external: Theorem A's soundness gap is built on Theorem 2.4, an unpublished preprint's fourth-root conversion. If that theorem were incorrect or had a different quantitative dependence, the reduction would lose its constant gap. This is exactly the concern the Reader identified as the weakest assumption. Since the concern is about an external result rather than an internal inconsistency, the Reader's conditional verdict remains appropriate: the main mathematical architecture is convincing, but the proof should explicitly cite and, if possible, verify the statement of [MdlS23] before the result can be considered fully self-contained.","tokens_in":26677,"tokens_out":50085,"duration_ms":465657,"concrete_test":"Independently verify Theorem 2.4 in [MdlS23] for a synchronous game with a 1/2-diagonally dominant distribution, and confirm that the deficit after symmetrization is O(ε^{1/4}) with a universal constant that does not depend on the number of questions. Concretely, re-derive the finite-dimensional case from [Vid22] and check whether the bound can be written as 1 - O((ε/C)^{1/4}) for all C-diagonally dominant games; if the correct exponent is α, recompute Theorem A's gap and test whether the target soundness 1 - O(ε^{8α}/t^{?}) remains bounded away from 0 for the fixed question size t in Corollary B.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reduction's soundness direction is calibrated exactly by the external theorem of Marrakchi and de la Salle (Theorem 2.4, [MdlS23]): a high quantum value for a C-diagonally dominant synchronous game is converted to a high synchronous quantum value with a deficit O((ε/C)^{1/4}). In the proof of Theorem A, this conversion is applied to the 1/2-diagonally dominant independent set game G' with ε' = ξ ε^8/t^4, yielding a synchronous-value deficit O(ξ^{1/4} ε^2/t). Lemma 5.1 then gives the opposite bound 1 - ζε^2/t, and the contradiction is obtained by choosing ξ small enough that κξ^{1/4} < ζ. Thus the ε^8 in the final gap is precisely the fourth power of the fourth-root conversion. If the true theorem had a weaker dependence—say a deficit O((ε/C)^β) with β < 1/4, or an added factor growing with t—the gap in Theorem A would shrink or disappear, and Corollary B's constant soundness gap for t-independent set games would not follow. The paper cites [MdlS23] as a preprint and does not reproduce its proof; the finite-dimensional case is attributed to [Vid22], but the exact dependence and constants are not independently checked here. This is the weakest point in the chain from synchronous games to independent set games.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a framework for gap-preserving reductions between gapped promise problems for nonlocal games and applies it to independent set games. The main result (Theorem A) reduces any synchronous game G with uniform question distribution to a diagonally weighted t-independent set game on its game graph X(G), preserving completeness (quantum value 1 maps to value 1) and giving a soundness gap: if ω*(G)<1−ε, then the independent set game has value <1−O(ε^8/t^4). Combining this with the Natarajan–Zhang family of constant-question-size synchronous games yields Corollary B: for some constants t and s, the (1,s)-gap* problem for t-independent set games is RE-complete. The proof relies on a new stability theorem (Theorem C and its extension Theorem 4.1) showing that a family of projections approximately summing to the identity can be rounded to a genuine PVM with error O(ε), polynomially improving on prior exponential bounds. A sharpness example (Proposition 6.2) shows that the t-dependence in Lemma 5.1 cannot be improved.","tokens_in":26974,"tokens_out":18017,"duration_ms":155409,"significance":"If correct, the result establishes independent set games as a natural MIP*-complete class, making the gapped promise problem for constant-question independent set games undecidable while the classical analogue is polynomial-time decidable. This is a substantive step in mapping the complexity landscape of MIP* and connects to the quantum PCP program. The paper is technically detailed: the stability theorem is proved from first principles with explicit constants, the reduction is fully specified, and the sharpness example is a valuable addition. The main caveat is that the soundness gap inherits the exact fourth-root dependence of the external theorem of Marrakchi and de la Salle (Theorem 2.4), so the stated gap is only as strong as that external result.","major_comments":[{"comment":"The soundness gap in Theorem A is quantitatively calibrated to the fourth-root conversion in Theorem 2.4, cited from the preprint [MdlS23]. In the proof, the constant ξ is chosen as ξ = ζ^4/κ^4 so that the contradiction follows from comparing κ(2ξ)^{1/4}ε^2/t with ζε^2/t. If the correct bound in Theorem 2.4 had a weaker exponent (β<1/4) or an additional dependence on the number of questions t, the gap O(ε^8/t^4) would shrink or disappear, and Corollary B would not follow. Because this is load-bearing for the central claim, the authors should either provide a self-contained proof of the needed form of Theorem 2.4 (in an appendix), or cite a published version and explicitly state the theorem and constant, and discuss the consequences of a weaker hypothesized dependence.","section":"Section 5, proof of Theorem A; Theorem 2.4"},{"comment":"The argument that the target soundness parameter s is positive by 'adding dummy bits to the original questions' is not substantiated and is likely incorrect as stated: inserting additional questions into a synchronous game with a uniform distribution changes the distribution and can alter the quantum value, so it is not clear that the resulting family remains RE-complete with the same gap. The existence of some t and s with s>0 only requires an appropriate choice of the source family in Theorem 2.13; the proof should be rephrased by choosing parameters from that theorem so that 1−O(ε^8/t^4)>0, rather than by a dummy-bit padding argument. As written, this step is a gap in the derivation of Corollary B.","section":"Section 5, proof of Corollary 5.3"}],"minor_comments":[{"comment":"The abstract says the gapped promise problem for independent set games is 'undecidable'; since the paper proves RE-completeness, it would be more precise to state RE-completeness directly. The same holds in the introduction's summary of Corollary B.","section":"Abstract and Section 1"},{"comment":"The parameter C is used both for the weight in the C-diagonally weighted version and for the dominance constant in C-diagonally dominant distributions, which can be confusing. Consider renaming one of them.","section":"Section 2, Definition 2.5"},{"comment":"The notation P_i^{(q,a)} is used before it is explicitly defined in the lemma; a short reminder that these are the PVM operators from the synchronous strategy of the independent set game would improve readability.","section":"Section 5, Lemma 5.1"},{"comment":"The sentence 'G is 1/2-diagonally dominant' should specify that it is the diagonally weighted independent set game G that is 1/2-diagonally dominant, to avoid confusion with the original game G.","section":"Section 5, proof of Theorem A"},{"comment":"A small typographical note: the expectation operator appears as 'Eq' in the display near equation (5.3); it should be typeset as \\mathbb{E}_q.","section":"Section 5, proof of Corollary 5.3"},{"comment":"The notation P^i_q for the deterministic strategy conflicts with the earlier notation P_i^{(q,a)}; aligning the notation would avoid confusion.","section":"Section 6, Proposition 6.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically strong and the central proof chain appears sound. The main risk is the reliance on the exact form of the external theorem [MdlS23] for the fourth-root conversion; the authors should seriously consider appending a proof of that theorem or ensuring it is published, since the final gap is engineered around it. The 'dummy bits' justification in Corollary 5.3 needs correction. If these are addressed, the paper would be a solid contribution to the MIP* complexity landscape."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid, genuinely useful paper. It lifts the MRV15 gapless reduction to a gap-preserving one, proves a clean linear stability theorem, and uses both to show that constant-question independent set games are MIP*-complete. The main chain is coherent, and the results are a real step forward for the quantum games complexity program.\n\nWhat is new: Theorem A gives a reduction from uniform synchronous games to t-independent set games with gap O(epsilon^8/t^4), which is exactly what is needed to turn the perfect-regime reduction into a complexity-theoretically meaningful reduction. The stability theorem (Theorem C / 4.1) improves the known exponential dependence on the number of operators to linear; that is a genuine technical contribution with independent value. Corollary B then follows cleanly from Natarajan-Zhang's constant-question synchronous games, and Section 6 honestly shows that the t-dependence in Lemma 5.1 is optimal. The paper is carefully written and the proofs are mostly self-contained.\n\nSoft spots, in proportion. First, the proof of Theorem A has a typo in the displayed use of Theorem 2.4: the fourth-root conversion should produce a deficit O(epsilon^2/t), not what the display appears to say. The intended calculation works, so this is minor, but it should be fixed before publication. Second, and more substantively, the soundness direction depends critically on the fourth-root conversion of Marrakchi-de la Salle, cited as a preprint and not proved here. That dependence is genuine: the epsilon^8 gap is exactly the fourth power of that fourth root. If the true exponent in [MdlS23] were worse, the constant gap in Corollary B would not follow. The paper is transparent about this in Remark 6.3, which mitigates the concern, but a referee should push the authors to state the dependence explicitly and confirm the preprint is available and stable. Third, the sharpness result only addresses Lemma 5.1, not the full reduction, so the t-dependence in Theorem A may not be optimal; the authors say so plainly.\n\nThe citation pattern is fine: the MRV15 gapless reduction is properly credited, the MdlS23 preprint is the right source for the conversion, and no fitted parameters are used. I think the reader's conditional verdict is right. Clean up the display, make the external dependency explicit, and this is publishable. The paper deserves a serious referee and will be useful to anyone working on MIP*, nonlocal games, or stability of POVMs.","headline":"A correct, valuable gap-preserving reduction from synchronous to independent set games, with a clean stability result; the main risks are a small display typo and an external preprint whose exact exponent the gap depends on.","tokens_in":27485,"tokens_out":5168,"would_cite":true,"duration_ms":46920,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q17","46L10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that independent set games—two-prover games where the verifier checks distinct non-adjacent answers—are MIP$^*$-complete via a gap-preserving reduction, making the constant-gap quantum value problem undecidable even…","keywords":["independent set games","nonlocal games","quantum value","gap-preserving reductions","RE-completeness","synchronous games","stability theorem","entangled provers"],"falsifier":"Construct a family of $m$ projections $p_1,\\dots,p_m$ in a matrix algebra with $\\|1-\\sum_{j=1}^m p_j\\|_2=\\varepsilon$ and compute the minimal possible $\\sum_{j=1}^m\\|p_j-q_j\\|_2^2$ over all PVMs $\\{q_j\\}$. Theorem C predicts this cost is at most a universal constant times $\\varepsilon$ for every $m$ and $\\varepsilon$; any family whose optimal rounding cost grows with $m$, or as $\\omega(\\varepsilon)$, would falsify the stability theorem and with it the soundness argument of Theorem A.","tokens_in":26512,"feed_emoji":"🎲","tokens_out":15548,"duration_ms":141141,"temperature":0.7,"pith_summary":"This paper establishes that independent set games—two-player games in which the verifier asks each prover for a vertex and accepts distinct non-adjacent vertices on different questions—are RE-complete in the entangled setting. The main theorem says that every synchronous game with uniform question distribution and $t$ questions can be turned into a $t$-independent set game whose quantum value is $1$ exactly when the original game has value $1$, and whose value falls below $1-O(\\varepsilon^8/t^4)$ whenever the original game falls below $1-\\varepsilon$. Since prior work supplies RE-complete families of synchronous games with constant question size and uniform distribution, the paper obtains a family of independent set games with fixed question size whose $(1,s)$-gap${}^*$ problem is RE-complete for some constant $s<1$, hence undecidable. In contrast, the classical version—deciding whether a given graph has an independent set of size $t$—is polynomial-time solvable by checking all $t$-subsets. The engine of the reduction is a new stability theorem showing that a family of projections whose sum is within $\\varepsilon$ of the identity in trace norm can be perturbed to a genuine projection-valued measure with total error $O(\\varepsilon)$, with no dependence on the number of projections.","feed_headline":"Entangled provers make independent set games undecidable","feed_subtitle":"For fixed question size, deciding between value 1 and value below a constant is undecidable; the classical version is in P.","key_machinery":"The central object is the game graph $X(G)$ of a synchronous game $G$: its vertices are question–answer pairs $(q,a)$, and two vertices are adjacent when the predicate rejects those answers in either order. The $t$-independent set game on $X(G)$ asks the provers to answer with vertices that are equal on equal questions and distinct and non-adjacent on different questions. In the perfect case, summing the independent-set-game projections over question labels gives the projections of a strategy for $G$; in the approximate case the paper needs Theorem C, which says that if projections $p_1,\\dots,p_m$ satisfy $\\|1-\\sum_j p_j\\|_2 \\le \\varepsilon$, then there exist projections $q_j$ with $\\sum_j q_j=1$ and $\\sum_j \\|p_j-q_j\\|_2^2 = O(\\varepsilon)$. This linear, parameter-free rounding—proved by adding an operator so the sum is at least one, rescaling to a POVM, and invoking the existing POVM orthogonalization theorem—is what turns a gapless reduction into a gap-preserving one.","core_discovery":"On the paper's own terms, the central discovery is that the gapless reduction of perfect strategies between synchronous games and independent set games survives when the strategies are only near-perfect, and the loss can be quantified. Theorem A states the precise transfer: for any synchronous game $G$ with uniform question distribution and $t$ questions, the diagonally weighted $t$-independent set game $G'$ on the game graph $X(G)$ satisfies $\\omega^*(G)=1 \\Rightarrow \\omega^*(G')=1$ and $\\omega^*(G)<1-\\varepsilon \\Rightarrow \\omega^*(G')<1-O(\\varepsilon^8/t^4)$. Feeding in the known RE-complete family of constant-question synchronous games yields Corollary B: there is a fixed integer $t$ and a constant $0