Gap-preserving reductions and RE-completeness of independent set games

Laura Man\v{c}inska; Matthijs Vernooij; Pieter Spaas; Taro Spirig

REVIEW 2 major objections 6 minor 1 cited by

Gap-preserving reductions and RE-completeness of independent set games

T0 review · 2 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2505.05253 v2 pith:7377X47N submitted 2025-05-08 quant-ph cs.CCmath.OA

Laura Mančinska , Pieter Spaas , Taro Spirig , Matthijs Vernooij This is my paper · ORCID

classification quant-phcs.CCmath.OA MSC 81P6868Q1746L10

keywords independentsetgamesnonlocalquantumvaluegap-preservingreductionsRE-completenesssynchronousstabilitytheorementangledprovers

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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<s<1$ such that the $(1,s)$-gap${}^*$ problem for $t$-independent set games is RE-complete. The same construction works for the commuting-operator value, so under the conjecture that the commuting-operator class equals coRE the problem becomes coRE-complete. The paper also shows the $t$-dependence in the soundness lemma is optimal for this construction, using a family of no-choice luck games.

Load-bearing premise

The soundness half of the reduction relies on a known conversion result that turns a near-perfect entangled strategy into a near-perfect synchronous strategy while losing only a fourth root of the diagonal-dominance gap, and if that conversion is weaker than stated, the constant gap $1-O(\varepsilon^8/t^4)$ would fail to follow.

Editorial extensions

If this is right

The $(1,s)$-gap${}^*$ problem for $t$-independent set games is undecidable for some fixed $t$ and constant $0<s<1$: no algorithm can distinguish quantum value $1$ from value below $s$.
Independent set games become a new MIP${}^*$-complete class, alongside synchronous and tailored games, giving later hardness reductions a more structured target with constant question size.
The classically trivial nature of the problem highlights the separation: entanglement makes a polynomially decidable promise problem undecidable.
Because the constant-question family has quasi-polynomial answer sets, the resulting graphs may be amenable to classical graph-compression techniques, opening a route toward the quantum games PCP conjecture.
The $t$-dependence in the soundness lemma cannot be improved for this construction: the luck-game example achieves the bound $1-2\varepsilon/t_n$ up to constants, ruling out replacement by $t^{\alpha}$ with $\alpha<1$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The new stability theorem is likely to outlive the specific reduction: any future work that needs to round approximate orthogonal projections without paying exponentially in the number of operators, for example in approximate versions of graph homomorphism games, can reuse Theorem C directly.
The sharpness result suggests that proving a gap independent of $t$ for arbitrary synchronous games would require abandoning the game-graph construction rather than tightening the analysis, since the present construction provably cannot deliver it.
Applying Theorem 4.1 to other known gapless reductions—for instance from 3-coloring games—is a natural next step; the linear rounding may convert their exponentially shrinking gaps into polynomial ones, though the paper does not claim this.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What 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.

Soft 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.

The 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.

Referee Report

2 major / 6 minor

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.

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 (2)

[Section 5, proof of Theorem A; Theorem 2.4] 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 5, proof of Corollary 5.3] 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.

minor comments (6)

[Abstract and Section 1] 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 2, Definition 2.5] 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 5, Lemma 5.1] 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 5, proof of Theorem A] 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 5, proof of Corollary 5.3] 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 6, Proposition 6.2] The notation P^i_q for the deterministic strategy conflicts with the earlier notation P_i^{(q,a)}; aligning the notation would avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the reduction's completeness and soundness steps are either proved in the paper or rest on external theorems; the only self-citation is reproved locally and is not load-bearing.

full rationale

The paper does not define its target in terms of its input nor rename a fitted quantity as a prediction. Theorem A constructs, for a synchronous game G with uniform distribution, the t-independent set game (X(G),t) on the game graph X(G). The completeness direction is taken from the gapless reduction of [MRV15], but the relevant Theorem 3.1 is restated and fully proved in Section 3 of the present paper, so the self-citation is not doing load-bearing work. The soundness direction is proved in the contrapositive in Lemma 5.1: a high synchronous value of the independent set game is rounded, via the new stability Theorem C (proved in Section 4 using the external orthogonalization theorem [dlS22, Theorem 1.2]), into a synchronous strategy for G with a controlled loss O(sqrt(t sqrt(delta))). The conversion from quantum value to synchronous quantum value in the proof of Theorem A uses Theorem 2.4, attributed to Marrakchi and de la Salle [MdlS23], with the finite-dimensional case attributed to Vidick [Vid22]; these are external authors and external results, not self-citations. The final gap O(epsilon^8/t^4) arises algebraically from composing the fourth-root deficit O((epsilon/C)^{1/4}) of Theorem 2.4 with the epsilon^2/t deficit of Lemma 5.1; no parameter is fitted to force the conclusion. The paper even flags in Remark 6.3 that it does not know whether the t-dependence in Theorem A is optimal and that Theorem 2.4 may itself be improvable, which further indicates that the argument is not circular: the claimed conclusion genuinely depends on an external theorem whose strength is not assumed by construction. Corollary B follows from Theorem A together with the external constant-question-size RE-complete family of Natarajan and Zhang [NZ23], again not self-cited. In summary, the central derivation is self-contained apart from standard external theorems and machine-independent published results, and no predicted quantity is equivalent to an input by definition.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on external theorems from the literature ([JNV+20b], [NZ23], [MdlS23], [PSS+16], [dlS22]) and standard operator-algebra background; none are introduced ad hoc, and no parameters are fitted.

assumptions (6)

standard math Theorem 2.13 (Natarajan-Zhang): there is an RE-complete succinct family of synchronous games with constant question size, uniform question distribution, and answer size polylog(n).
The RE-hardness for independent set games starts from this family; Corollary B inherits RE-completeness from it.
standard math Theorem 2.4 (Marrakchi-de la Salle): for a C-diagonally dominant synchronous game, high quantum value implies high synchronous quantum value with O((epsilon/C)^(1/4)) loss.
Invoked in the proof of Theorem A to pass from a high quantum value of the independent set game to a high synchronous quantum value.
standard math Theorem 2.2 (Paulsen-Severini-Stahlke-Todorov-Winter): synchronous correlations correspond to PVMs in tracial von Neumann algebras.
The strategy-level proofs in Sections 3 and 5 are formulated as relations among projections; this theorem justifies that representation.
standard math [dlS22, Theorem 1.2] (de la Salle): a POVM with tau(sum a_j^2) > 1-epsilon' is close to a PVM in 2-norm.
Theorem 4.1 reduces the projection-rounding problem to this external orthogonalization theorem.
standard math MIP*=RE [JNV+20b], the equality used to identify RE-completeness with MIP*-completeness.
Used for interpreting the result and for the statement of Corollary B.
standard math Standard tracial von Neumann algebra framework: finite von Neumann algebras admit faithful normal tracial states and the associated 2-norm.
Throughout the proof, projections are manipulated in tracial von Neumann algebras; bicommutant and trace properties are background.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Gap-preserving reductions and RE-completeness of independent set games." pith.science (2026). https://pith.science/paper/7377X47N

@misc{pith2026250505253,
  author       = {Pith},
  title        = {Pith review of: Gap-preserving reductions and RE-completeness of independent set games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7377X47N}},
  note         = {Machine review of arXiv:2505.05253}
}

abstract

In complexity theory, gap-preserving reductions play a crucial role in studying hardness of approximation and in analyzing the relative complexity of multiprover interactive proof systems. In the quantum setting, multiprover interactive proof systems with entangled provers correspond to gapped promise problems for nonlocal games, and the recent result MIP$^*$=RE \cite{ji2020mipre} shows that these are in general undecidable. However, the relative complexity of problems within MIP$^*$ is still not well-understood, as establishing gap-preserving reductions in the quantum setting presents new challenges. In this paper, we introduce a framework to study such reductions and use it to establish MIP$^*$-completeness of the gapped promise problem for the natural class of independent set games. In such a game, the goal is to determine whether a given graph contains an independent set of a specified size. We construct families of independent set games with constant question size for which the gapped promise problem is undecidable. In contrast, the same problem is decidable in polynomial time in the classical setting. To carry out our reduction, we establish a new stability theorem, which could be of independent interest, allowing us to perturb families of almost PVMs to genuine PVMs.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Existence and nonexistence of commutativity gadgets for entangled CSPs
quant-ph 2025-09 conditional novelty 8.0 of 10

A CSP whose quantum endomorphism monoid is non-classical admits no commutativity gadget; in particular, k-colouring for k at least 4 has no commutativity gadget, while an oracular commutativity gadget exists.

Reference graph

Works this paper leans on

15 extracted references · 5 canonical work pages · cited by 1 Pith paper

[4]

Efficiently stable presentations from error-correcting codes.preprint, arXiv:2311.04681,

[CVY23] Michael Chapman, Thomas Vidick, and Henry Yuen. Efficiently stable presentations from error-correcting codes.preprint, arXiv:2311.04681,

arXiv
[5]

[Har24b] Samuel J. Harris. Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem. preprint, arXiv:2412.19405,

work page Pith review arXiv
[10]

Almost synchronous correlations and Tomita- Takesaki theory.preprint, arXiv:2307.08129,

[MdlS23] Amine Marrakchi and Mikael de la Salle. Almost synchronous correlations and Tomita- Takesaki theory.preprint, arXiv:2307.08129,

arXiv
[12]

The status of the quantum PCP conjecture (games version)

[NN24] Anand Natarajan and Chinmay Nirkhe. The status of the quantum PCP conjecture (games version). preprint, arXiv:2403.13084,

arXiv
[1998]

The Aldous–Lyons conjecture I: Subgroup tests.preprint, arXiv:2408.00110,

[BCLV24] Lewis Bowen, Michael Chapman, Alexander Lubotzky, and Thomas Vidick. The Aldous–Lyons conjecture I: Subgroup tests.preprint, arXiv:2408.00110,

arXiv
[2004]

RE-completeness of entangled constraint satisfaction problems

[CM24] Eric Culf and Kieran Mastel. RE-completeness of entangled constraint satisfaction problems. preprint, arXiv:2410.21223,

arXiv
[2010]

Tracial embeddable strategies: Lifting MIP* tricks to MIP co

[Lin24] Junqiao Lin. Tracial embeddable strategies: Lifting MIP* tricks to MIP co. preprint, arXiv:2304.01940,

work page arXiv
[2012]

Binary constraint system games and locally commutative reductions

[Ji13] Zhengfeng Ji. Binary constraint system games and locally commutative reductions. preprint, arXiv:1310.3794,

arXiv

Show all 15 references

[2014]

Roberson, and Antonios Varvitsiotis

[MRV15] Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis. On deciding the existence of perfect entangled strategies for nonlocal games.Chic. J. Theor. Comput. Sci., 2016(5),

2016
[2017]

[JNV+20a] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*=RE. preprint, arXiv:2001.04383,

2001 arXiv
[2020]

Quan- tum soundness of the classical low individual degree test.preprint, arXiv:2009.12982,

[JNV+20b] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. Quan- tum soundness of the classical low individual degree test.preprint, arXiv:2009.12982,

2009 arXiv
[2021]

Rounding near-optimal quantum strategies for nonlocal games to strategies using maximally entangled states.preprint, arXiv:2203.02525,

[Pad25] Connor Paddock. Rounding near-optimal quantum strategies for nonlocal games to strategies using maximally entangled states.preprint, arXiv:2203.02525,
[2022]

Lifting the maximally-entangledness assumption in robust self-testing for synchronous games, 2025

[VZ25] Matthijs Vernooij and Yuming Zhao. Lifting the maximally-entangledness assumption in robust self-testing for synchronous games, 2025

2025
[2024]

The Aldous–Lyons conjecture II: Undecidability.preprint, arXiv:2501.00173,

27 References [BCV24] Lewis Bowen, Michael Chapman, and Thomas Vidick. The Aldous–Lyons conjecture II: Undecidability.preprint, arXiv:2501.00173,

arXiv
[2025]

Satisfiability problems and algebras of boolean constraint system games.preprint, arXiv:2310.07901,

[PS23] Connor Paddock and William Slofstra. Satisfiability problems and algebras of boolean constraint system games.preprint, arXiv:2310.07901,

arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [4]

Efficiently stable presentations from error-correcting codes.preprint, arXiv:2311.04681,

[CVY23] Michael Chapman, Thomas Vidick, and Henry Yuen. Efficiently stable presentations from error-correcting codes.preprint, arXiv:2311.04681,

arXiv

[2] [5]

[Har24b] Samuel J. Harris. Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem. preprint, arXiv:2412.19405,

work page Pith review arXiv

[3] [10]

Almost synchronous correlations and Tomita- Takesaki theory.preprint, arXiv:2307.08129,

[MdlS23] Amine Marrakchi and Mikael de la Salle. Almost synchronous correlations and Tomita- Takesaki theory.preprint, arXiv:2307.08129,

arXiv

[4] [12]

The status of the quantum PCP conjecture (games version)

[NN24] Anand Natarajan and Chinmay Nirkhe. The status of the quantum PCP conjecture (games version). preprint, arXiv:2403.13084,

arXiv

[5] [1998]

The Aldous–Lyons conjecture I: Subgroup tests.preprint, arXiv:2408.00110,

[BCLV24] Lewis Bowen, Michael Chapman, Alexander Lubotzky, and Thomas Vidick. The Aldous–Lyons conjecture I: Subgroup tests.preprint, arXiv:2408.00110,

arXiv

[6] [2004]

RE-completeness of entangled constraint satisfaction problems

[CM24] Eric Culf and Kieran Mastel. RE-completeness of entangled constraint satisfaction problems. preprint, arXiv:2410.21223,

arXiv

[7] [2010]

Tracial embeddable strategies: Lifting MIP* tricks to MIP co

[Lin24] Junqiao Lin. Tracial embeddable strategies: Lifting MIP* tricks to MIP co. preprint, arXiv:2304.01940,

work page arXiv

[8] [2012]

Binary constraint system games and locally commutative reductions

[Ji13] Zhengfeng Ji. Binary constraint system games and locally commutative reductions. preprint, arXiv:1310.3794,

arXiv