Quantum Perfect Matchings

David Cui; David E. Roberson; Laura Man\v{c}inska; Seyed Sajjad Nezhadi

REVIEW 2 major objections 5 minor 23 references

Quantum Perfect Matchings

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

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

Pith's one-line read Quantum perfect matchings exist exactly when a graph's line graph has a maximal projective packing.

desk verdict Fresh family of matching games with solid graph-level characterizations; the hypergraph undecidability proof is broken as written. read the letter →

arxiv 2502.05136 v1 pith:CK2QYXTB submitted 2025-02-07 quant-ph

David Cui , Laura Mančinska , Seyed Sajjad Nezhadi , David E. Roberson This is my paper · ORCID

classification quant-ph MSC 05C7005C6981P68

keywords quantumperfectmatchingnonlocalgameslinegraphprojectivepackingindependencenumbernonsignalingstrategiesfractionalundecidability

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 defines nonlocal games that test for perfect matchings, L-perfect matchings in bipartite graphs, fractional perfect matchings, and hypergraph perfect matchings, and then uses perfect quantum and nonsignaling strategies for these games to define quantum and nonsignaling versions of matchings. The central claim is that these quantum versions are genuinely new properties: odd complete graphs $K_n$ for $n \geq 7$ have quantum perfect matchings despite having no classical perfect matching, while odd cycles $C_n$ for $n \geq 5$ have nonsignaling perfect matchings despite having neither classical nor quantum ones. The paper gives combinatorial characterizations: a graph has a quantum perfect matching exactly when its line graph admits a projective packing of value $|V(G)|/2$, equivalently when the quantum independence number of the doubled line graph is $|V(G)|$; and a graph has a nonsignaling perfect matching exactly when it has a fractional perfect matching that avoids triangles. It also shows that bipartite L-perfect matching games are quantum sound, so quantum entanglement cannot fool them, and that deciding quantum perfect matchings for hypergraphs is undecidable. A reader should care because these results transplant a classical matching condition into the quantum graph-theory toolkit and give finitary combinatorial handles on properties defined through high-dimensional operator strategy spaces.

What carries the argument

The central objects are the synchronous nonlocal games $\mathrm{PM}_G$ and $\mathrm{BPM}_G$, where each player answers a vertex with an edge incident to it and two answers must be either identical or vertex-disjoint; a perfect classical strategy is exactly a perfect (or L-perfect) matching. The argument is carried by the equivalence in Theorem 6.4, which transfers a perfect quantum strategy for $\mathrm{PM}_G$ into a projective packing of the line graph $L(G)$ — an assignment of mutually orthogonal projections to adjacent edges, with value $|V(G)|/2$ — and then into a quantum independent set of the doubled line graph $2L(G)$, using the known inequality $\alpha_q \le \alpha_p$. On the nonsignaling side, the machinery is a direct construction: from any perfect nonsignaling strategy the marginal probabilities define a fractional perfect matching, and conversely any rational triangle-avoiding fractional perfect matching is converted into a perfect nonsignaling correlation by a Hall's theorem argument on an auxiliary bipartite graph.

What would settle it

Find a graph $G$ for which $L(G)$ admits a projective packing of value $|V(G)|/2$ but $\mathrm{PM}_G$ has no perfect quantum strategy, equivalently with $\alpha_q(2L(G)) < |V(G)|$; such a graph would break the second implication of Theorem 6.4. A concrete place to look is the missing rounding step from a projective packing to a quantum independent set, since that step is the only unproven part of the equivalence.

Watch

Extended reading notes

Core claim

The paper's load-bearing equivalence is Theorem 6.4: for any graph $G$, $G$ has a quantum perfect matching if and only if the line graph $L(G)$ has a projective packing of value $|V(G)|/2$, if and only if $\alpha_q(2L(G)) = |V(G)|$, where $\alpha_q$ is the quantum independence number. A projective packing assigns projections to vertices so that adjacent vertices receive orthogonal projections, and its value is the average trace of those projections; this mirrors the classical fact that $G$ has a perfect matching exactly when the independence number of $L(G)$ is $|V(G)|/2$. On the nonsignaling side, Theorem 6.10 identifies nonsignaling perfect matchings with fractional perfect matchings whose total weight on every triangle is at most $1$, which yields the odd-cycle examples. The paper also fully characterizes nonsignaling L-perfect matchings in bipartite graphs, proves that among the complete bipartite graphs $K_{n,2}$ only $K_{3,2}$ displays quantum advantage with value $5/6$ against a classical value of $7/9$, and shows that deciding quantum perfect matchings for hypergraphs is undecidable.

Load-bearing premise

The central claim rests on the assumption that any projective packing of the line graph can be converted into a quantum independent set of the doubled line graph; the paper states this follows from an earlier discussion but gives no derivation or citation for that conversion.

Editorial extensions

If this is right

Complete graphs $K_n$ with odd $n \geq 7$ are quantum perfect matchable, so the quantum property strictly extends classical perfect matching and is not merely a fractional relaxation.
The equivalence with projective packings of line graphs gives a finite-dimensional operator-algebraic certificate for quantum perfect matchings, reducing the graph decision problem to deciding whether $\alpha_q(2L(G))$ is maximal.
Odd cycles $C_n$ for $n \geq 5$ are nonsignaling perfect matchable but not quantum or classical, so nonsignaling matchings form a strictly broader class than quantum matchings.
Bipartite L-perfect matching games are quantum sound, and among $K_{n,2}$ the only quantum advantage is $K_{3,2}$, where the quantum value is $5/6$ versus the classical value $7/9$.
Quantum perfect matching for hypergraphs is undecidable, so any decidability result for graphs would have to use graph-specific structure rather than a direct hypergraph reduction.

Reading between the lines

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

If the missing conversion in Theorem 6.4 can be supplied, the complexity of quantum perfect matching in graphs would coincide with the complexity of quantum independence restricted to doubled line graphs; the paper's hypergraph reduction suggests that undecidability may transfer only when this conversion holds.
The fractional-perfect-matching characterization of nonsignaling matchings points to a natural strengthening: if every triangle-avoiding fractional perfect matching can be chosen with weights in $\{0,1/2,1\}$, nonsignaling perfect matchings would decompose into odd cycles of length at least 5 and ordinary matchings.
The use of a Kochen-Specker construction for $K_7$ hints that quantum perfect matchings are a contextuality phenomenon; exploring whether all quantum-only matchable graphs arise from Kochen-Specker-type projection packings could connect matching games to broader contextuality results.
For bipartite graphs, the nonsignaling characterization in terms of left-degree-2 subgraphs suggests a purely combinatorial interpretation of nonsignaling correlations as fractional edge covers, which might extend to other graph properties such as quantum edge coloring.

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: read this for the graph results, not for the undecidability claim. The paper introduces perfect matching games for graphs and hypergraphs, and the graph-level theory holds up well. The nonsignaling characterizations (Theorem 4.3 and Theorem 6.10) are real: the first gives a clean combinatorial condition on the bipartite graph, and the second connects perfect nonsignaling strategies to fractional perfect matchings avoiding triangles. The K_{n,2} quantum value computation is explicit, including sum-of-squares certificates and a full characterization of optimal strategies. The equivalence of quantum perfect matchings with projective packings of line graphs is a genuinely useful bridge to the existing quantum independence framework, and the proof that K_7 works via Kochen-Specker sets while K_5 does not is a nice concrete demonstration.

The soft spots are concentrated in Section 6.3. Theorem 6.11 claims undecidability of quantum perfect matchings for hypergraphs by reducing to α_q(2L(H)). But Theorem 6.4 is proved only for graphs, and the proof uses that each edge is incident to exactly two vertices. For a hyperedge of size k, the trace identity becomes k Σ_e Π_e = Σ_x Σ_{e∋x} Π_e, so the projective packing value is |V|/k, not |V|/2, and the converse step forcing Σ_{e∋x} Π_e = I has no analogue. The claimed equivalence is outright false: for H = ({1,2,3}, {{1,2,3}}), H has a classical perfect matching, so a perfect quantum strategy, but L(H)=K_1 and α_q(2L(H))=2≠3=|V(H)|. So the undecidability theorem may still be true, but this argument does not establish it.

A smaller issue: the step (2)⇔(3) in Theorem 6.4 is waved at with "follows from the above discussion." The forward direction (quantum independent set to projective packing) is standard, but the converse needs an argument; it is patchable (use the upper bound on projective packings of L(G), then split the packing of 2L(G)), but as written it is load-bearing and unproved. The reliance on the authors' own projective packing framework is not itself a problem; this is a proof gap, not a citation issue.

The prose is fine, the definitions are careful, and the graph-theoretic derivations are mostly readable. The paper deserves a serious referee; the hypergraph section needs either a repaired reduction or an explicit flag that the undecidability claim is not established here.

Referee Report

2 major / 5 minor

Summary. The paper introduces synchronous nonlocal games that classically test L-perfect matchings in bipartite graphs, perfect matchings in graphs and hypergraphs, and fractional perfect matchings. It defines quantum and nonsignaling versions of these properties and derives characterizations: bipartite L-perfect matching games are quantum sound; the K_{n,2} games have exact quantum and classical values; nonsignaling perfect matching is equivalent to a fractional perfect matching avoiding triangles; and a graph has a quantum perfect matching iff its line graph has a projective packing of value |V|/2, claimed iff alpha_q(2L(G)) = |V|. It further claims undecidability of quantum perfect matching for hypergraphs.

Significance. The graph-level results are valuable: the nonsignaling characterization via fractional perfect matchings is clean and appears correct, the K_{n,2} analysis gives an exact quantum value with sum-of-squares certificates, and the equivalence of quantum perfect matching with projective packings of line graphs is conceptually appealing. The paper makes its definitions precise and includes constructive arguments, such as explicit nonsignaling strategies and a Hall-theorem rounding argument. However, the two proof gaps described below affect a key part of the main characterization and the headline undecidability result, so the paper requires substantial revision.

major comments (2)

[6.1, Theorem 6.4] The equivalence (2) <=> (3) is not established. The proof says it follows from the above discussion, but the discussion only proves alpha_q(G) <= alpha_p(G). A projective packing of L(G) of value |V|/2 yields alpha_p(2L(G)) >= |V|, and the trace argument gives alpha_p(2L(G)) <= |V|, so alpha_p(2L(G)) = |V|. However, this only gives alpha_q(2L(G)) <= |V|; the needed lower bound alpha_q(2L(G)) >= |V| requires a construction of a quantum |V|-independent set of 2L(G) from the projective packing, or a cited theorem to that effect. Please provide this construction/reference, or remove item (3) from the theorem.
[6.3, Theorem 6.11] The proof of undecidability for hypergraphs applies Theorem 6.4, which is proved only for graphs. For a hyperedge e of size k, the trace identity 2 * sum_e Pi_e = sum_x sum_{e contains x} Pi_e fails; each hyperedge is counted k times instead of twice. Consequently, a perfect quantum strategy for PM_H does not yield a projective packing of L(H) of value |V(H)|/2, and the converse trace argument also has no analogue. The claimed equivalence is in fact false: for H = ({1,2,3}, {{1,2,3}}), PM_H has a perfect classical strategy, but L(H) = K1, so 2L(H) = K1 union K1 and alpha_q(2L(H)) = 2, whereas |V(H)| = 3. Thus the reduction used to prove undecidability is invalid, and the undecidability of quantum perfect matching for hypergraphs is not established by this argument.

minor comments (5)

[2.1, Definition 2.5] The phrase 'two collections of mutually commuting PVMs' is ambiguous; it should state explicitly that Alice's measurements commute with Bob's measurements, as in the displayed condition.
[4.2, Theorem 4.3 proof] There is a typo: 'N(v1∩N(v2)' should be 'N(v1)∩N(v2)', and later 'G has a perfect nonsignaling matching if and only if G does' is missing the second 'G#'.
[5, Lemmas 5.1-5.2] The summation 'sum_{v in [v]}' should read 'sum_{v in [n]}', and the norm notation ||·||_rho is used before being defined; please define it explicitly.
[6.1, Lemma 6.5] In the proof, the symbol i is used as a vertex index in 'sum_{i != a} Pi_{(i,a)}', which conflicts with the use of i as a color index in Definition 6.3; use a different letter such as u or v.
[Abstract] The first bullet says 'complete combinatorial characterizations' but should be singular 'characterization' for the nonsignaling matching result.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main equivalences are substantive; the hypergraph undecidability argument has a non-circular correctness gap.

full rationale

I examined the derivation chain for self-definition, fitted-input predictions, and self-citation smuggling. The perfect matching game (Definition 3.3), projective packing (Definition 6.2), and quantum independence number (Definition 6.3) are defined independently; Theorem 6.4's proof of (1)⇔(2) uses the trace identity 2∑_{e∈E(G)}Π_e = ∑_{x∈V(G)}∑_{e∋x}Π_e to convert a quantum strategy into a packing and back, with no fitted parameter or normalization chosen to force the conclusion. The step labeled '(2)⇔(3) follows from the above discussion' is underproved: the paper only states α_q≤α_p and needs a converse for doubled line graphs that is not derived. That is a missing argument, not a circular reduction; no equation in the paper identifies α_q(2L(G))=|V(G)| with the definition of quantum perfect matching by construction. The same is true of the hypergraph undecidability proof in Section 6.3: Theorem 6.4 is graph-only because the coefficient 2 in the trace identity counts two endpoints per edge; for a hyperedge of size k the identity becomes ∑_{e∋x}Π_e counted k times, so the claimed equivalence α_q(2L(H))=|V(H)| is not established. This is a serious correctness gap in the reduction to [Har23], but it is an invalid theorem application rather than circularity. Self-citations to [MRV15, Rob13, MR16] supply definitions and the elementary inequality α_q≤α_p; they do not assume the paper's target equivalence, and no uniqueness theorem or ansatz is smuggled in via those citations. I therefore find no significant circularity.

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

The central claims rest on standard graph theory and prior nonlocal game results. There are no fitted numerical parameters and no newly postulated physical entities. The main unstated burden is the missing projection packing to quantum independent set conversion used in Theorem 6.4(3), which also underpins the flawed hypergraph undecidability proof.

assumptions (6)

standard math Hall's marriage theorem (Theorem 2.18)
Used to prove quantum soundness of the bipartite matching game in Theorem 4.1 and the classical characterization in Theorem 3.2.
standard math Every synchronous game with a perfect strategy has a perfect synchronous strategy in classical, quantum, commuting-operator, and nonsignaling settings (Theorem 2.8 from HMN+21)
Reduces general perfect strategies to synchronous ones, allowing Lemma 6.1 and Theorem 3.2 to analyze strategies via a single set of projectors or a single response function.
standard math Fractional perfect matchings can be taken with values in {0, 1/2, 1}, equivalently a decomposition into matchings and odd cycles (Theorem 2.17 from SU13)
Used in Lemma 3.6 to connect fractional perfect matchings to L-perfect matchings of the bipartite double cover.
domain assumption Existence of a Kochen-Specker set with seven contexts providing a projective packing of L(K7) of value 7/2 (LBPC14)
Basis for Lemma 6.6 that K7 has a quantum perfect matching; the construction is external to the paper.
domain assumption Undecidability of deciding the quantum independence number of graphs (Har23)
Used in Theorem 6.11 to conclude undecidability of quantum perfect matching for hypergraphs, contingent on the flawed reduction.
standard math The converse of α_q ≤ α_p for doubled line graphs, i.e. that projective packings of L(G) of value |V|/2 imply α_q(2L(G)) = |V|
The paper states only α_q ≤ α_p explicitly but relies on the unproved converse for Theorem 6.4(3). No citation or proof is given for the rounding step.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum Perfect Matchings." pith.science (2026). https://pith.science/paper/CK2QYXTB

@misc{pith2026250205136,
  author       = {Pith},
  title        = {Pith review of: Quantum Perfect Matchings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CK2QYXTB}},
  note         = {Machine review of arXiv:2502.05136}
}

abstract

We investigate quantum and nonsignaling generalizations of perfect matchings in graphs using nonlocal games. Specifically, we introduce nonlocal games that test for $L$-perfect matchings in bipartite graphs, perfect matchings in general graphs and hypergraphs, and fractional perfect matchings. Our definitions come from the fact that these games are classical property tests for the corresponding matching conditions. We use the existence of perfect quantum and nonsignaling strategies for these games to define quantum and nonsignaling versions of perfect matchings. Finally, we provide characterizations of when graphs exhibit these extended properties: - For nonsignaling matchings, we give a complete combinatorial characterizations. In particular, a graph has a nonsignaling perfect matching if and only if it admits a fractional perfect matching that has bounded value on triangles. \item In bipartite graphs, the nonsignaling $L$-perfect matching property is achieved exactly when the left component of the graph can be split into two disjoint subgraphs: one with a classical $L$-perfect matching and another with left-degree 2. - In the quantum setting, we show that complete graphs $K_n$ with odd $n \geq 7$ have quantum perfect matchings. We prove that a graph has a quantum perfect matching if and only if the quantum independence number of its line graph is maximal, extending a classical relationship between perfect matchings and line graph independence numbers. - For bipartite graphs, we establish that the $L$-perfect matching game does not exhibit quantum pseudotelepathy, but we characterize the quantum advantage for complete bipartite graphs $K_{n,2}$. - Additionally, we prove that deciding quantum perfect matchings in hypergraphs is undecidable and leave open the question of its complexity in graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 21 canonical work pages

[1]

Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis

Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory, Series B , 136:289--328, 2019

work page 2019
[2]

Hypergraphs: Combinatorics of finite sets, 1984

Claude Berge. Hypergraphs: Combinatorics of finite sets, 1984

work page 1984
[3]

Cameron, Ashley Montanaro, Michael W

Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and Andreas Winter. On the quantum chromatic number of a graph, 2006

work page 2006
[4]

Introduction to Property Testing

Oded Goldreich. Introduction to Property Testing . Cambridge University Press, 2017

2017
[5]

Samuel J. Harris. Universality of graph homomorphism games and the quantum coloring problem, 2023

work page 2023
[6]

William Helton, Hamoon Mousavi, Seyed Sajjad Nezhadi, Vern I

J. William Helton, Hamoon Mousavi, Seyed Sajjad Nezhadi, Vern I. Paulsen, and Travis B. Russell. Synchronous values of games, 2021

work page 2021
[7]

The np-completeness of edge-coloring

Ian Holyer. The np-completeness of edge-coloring. SIAM Journal on Computing , 10(4):718--720, 1981

1981
[8]

A multi-prover interactive proof for nexp sound against entangled provers, 2012

Tsuyoshi Ito and Thomas Vidick. A multi-prover interactive proof for nexp sound against entangled provers, 2012

work page 2012

Show all 23 references

[9]

Binary constraint system games and locally commutative reductions, 2013

Zhengfeng Ji. Binary constraint system games and locally commutative reductions, 2013

2013
[10]

Quantum soundness of the classical low individual degree test, 2020

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. Quantum soundness of the classical low individual degree test, 2020

2020
[11]

Mip*=re, 2022

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. Mip*=re, 2022

2022
[12]

Quantum soundness of testing tensor codes

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. Quantum soundness of testing tensor codes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 586--597, 2022

2021
[13]

Portillo, and Adan Cabello

Petr Lisonek, Piotr Badziag, Jose R. Portillo, and Adan Cabello. Kochen-specker set with seven contexts. Physical Review A , 89(4), April 2014

2014
[14]

Nonlocal games, compression theorems, and the arithmetical hierarchy

Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen. Nonlocal games, compression theorems, and the arithmetical hierarchy. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , STOC ’22, page 1–11. ACM, June 2022

2022
[15]

Roberson

Laura Mančinska and David E. Roberson. Quantum homomorphisms. Journal of Combinatorial Theory, Series B , 118:228--267, 2016

2016
[16]

Roberson

Laura Mančinska and David E. Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 661--672, 2020

2020
[17]

Deciding the existence of perfect entangled strategies for nonlocal games

Laura Man c inska, David E Roberson, and Antonios Varvitsiotis. Deciding the existence of perfect entangled strategies for nonlocal games. arXiv preprint arXiv:1506.07429 , 2015

2015 arXiv
[18]

A quantum linearity test for robustly verifying entanglement

Anand Natarajan and Thomas Vidick. A quantum linearity test for robustly verifying entanglement. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , STOC ’17, page 1003–1015. ACM, June 2017

2017
[19]

Variations on a theme: Graph homomorphisms

David E Roberson. Variations on a theme: Graph homomorphisms. 2013

2013
[20]

Tsirelson's problem and an embedding theorem for groups arising from non-local games

William Slofstra. Tsirelson's problem and an embedding theorem for groups arising from non-local games. Journal of the American Mathematical Society , 33(1):1--56, sep 2019

2019
[21]

Kochen specker sets and the rank-1 quantum chromatic number

Giannicola Scarpa and Simone Severini. Kochen specker sets and the rank-1 quantum chromatic number. IEEE Transactions on Information Theory , 58(4):2524--2529, apr 2012

2012
[22]

Scheinerman and Daniel H

Edward R. Scheinerman and Daniel H. Ullman. Fractional Graph Theory: a Rational Approach to the Theory of Graphs . Dover Publications, Minola, N.Y., 2013

2013
[23]

W. T. Tutte. The Factorization of Linear Graphs . Journal of the London Mathematical Society , s1-22(2):107--111, 04 1947

1947

Pith tools

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

[1] [1]

Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis

Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory, Series B , 136:289--328, 2019

work page 2019

[2] [2]

Hypergraphs: Combinatorics of finite sets, 1984

Claude Berge. Hypergraphs: Combinatorics of finite sets, 1984

work page 1984

[3] [3]

Cameron, Ashley Montanaro, Michael W

Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and Andreas Winter. On the quantum chromatic number of a graph, 2006

work page 2006

[4] [4]

Introduction to Property Testing

Oded Goldreich. Introduction to Property Testing . Cambridge University Press, 2017

2017

[5] [5]

Samuel J. Harris. Universality of graph homomorphism games and the quantum coloring problem, 2023

work page 2023

[6] [6]

William Helton, Hamoon Mousavi, Seyed Sajjad Nezhadi, Vern I

J. William Helton, Hamoon Mousavi, Seyed Sajjad Nezhadi, Vern I. Paulsen, and Travis B. Russell. Synchronous values of games, 2021

work page 2021

[7] [7]

The np-completeness of edge-coloring

Ian Holyer. The np-completeness of edge-coloring. SIAM Journal on Computing , 10(4):718--720, 1981

1981

[8] [8]

A multi-prover interactive proof for nexp sound against entangled provers, 2012

Tsuyoshi Ito and Thomas Vidick. A multi-prover interactive proof for nexp sound against entangled provers, 2012

work page 2012