Pith. sign in

REVIEW 3 major objections 5 minor 65 references

The Aldous--Lyons Conjecture II: Undecidability

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

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

Pith's one-line read Distinguishing tailored non-local games with perfect strategies from those with quantum value below 1/2 is undecidable.

desk verdict A serious, well-structured claim of TailoredMIP*=RE with the crux deferred to later sections; deserves a rigorous referee. read the letter →

arxiv 2501.00173 v1 pith:2VED3PRP submitted 2024-12-30 quant-ph math.COmath.GRmath.PR

Lewis Bowen , Michael Chapman , Thomas Vidick This is my paper · ORCID
classification quant-phmath.COmath.GRmath.PR MSC 03D3568Q17
keywords Aldous–Lyonsconjecturetailorednon-localgamesundecidabilitynon-soficunimodularnetworksMIP*=REcompressionprobabilisticallycheckableproofsConnesembeddingproblem
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 proves an undecidability gap for tailored non-local games: there is a polynomial-time construction taking any Turing machine $M$ to a tailored non-local game $G_M$ such that $M$ halts exactly when $G_M$ has a perfect Z-aligned permutation strategy that commutes along edges (ZPC). When $M$ never halts, every synchronous quantum strategy wins $G_M$ with probability less than 1/2. This establishes $\mathrm{TailoredMIP}^* = \mathrm{RE}$, a strengthening of the earlier $\mathrm{MIP}^* = \mathrm{RE}$ theorem, and, via the reduction in the companion paper, implies the existence of non-sofic unimodular networks and therefore refutes the Aldous–Lyons conjecture. It also reproves the negative solution of Connes' embedding problem with a streamlined argument.

What carries the argument

The load-bearing mechanism is the Compression Theorem, applied to tailored normal-form verifiers (TNFV), finite Turing-machine presentations of tailored games. Compression combines question reduction, answer reduction, and anchored parallel repetition. Question reduction uses an introspection game and a robust self-test of the Pauli group to force the provers to sample their own questions from the right distribution. Answer reduction is a tailor-made probabilistically checkable proof: the players encode their answers in an error-correcting code, and the construction ensures that any encoded bit that depends on an unreadable answer bit does so linearly, because the readable part allows non-linear checks while the unreadable part must remain controlled-linear. The crucial structural fact is that the AND of two Z-aligned permutations is again a Z-aligned permutation, which fails for general permutation strategies. Anchored parallel repetition restores the soundness parameter. The fixed-point verifier $V_{M,\lambda}$ iterates compression to simulate the Halting problem.

What would settle it

Take a Turing machine $M$ known independently not to halt, construct $G_M$ from the explicit polynomial-time procedure, and search over finite-dimensional synchronous quantum strategies—for example by an increasing sequence of semidefinite relaxations—for one winning with probability at least 1/2; finding one would falsify the soundness claim. For a halting $M$, checking that the explicit Z-aligned permutation strategy wins all questions is a finite verification whose failure would falsify completeness.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2.31: $\mathrm{TailoredMIP}^* = \mathrm{RE}$. There is a polynomial-time algorithm that maps a Turing machine $M$ to a tailored non-local game $G_M$ whose question sampling and decision predicate are polynomial-time computable. If $M$ halts, $G_M$ has a perfect Z-aligned permutation strategy that commutes along edges, so $\mathrm{val}^*(G_M)=1$. If $M$ never halts, $\mathrm{val}^*(G_M)<1/2$. The theorem is derived from a compression theorem for tailored normal-form verifiers: a reduction in question and answer length that preserves perfect ZPC strategies and amplifies the entanglement needed to win with probability 1/2. The Halting-problem reduction is obtained from a fixed-point verifier that is its own compression exactly until the machine halts.

Load-bearing premise

The main theorem rests on the Compression Theorem; its load-bearing premise is that answer reduction can be implemented for tailored verifiers so that every encoded bit depending on an unreadable answer bit depends on it linearly—if this tailored probabilistic checking step fails, the fixed-point reduction to the Halting problem breaks.

Editorial extensions

If this is right

  • If the theorem is correct, the Aldous–Lyons conjecture is false: the companion reduction converts any tailored game with the Theorem 2.31 gap into a unimodular network that is not sofic.
  • The same undecidability equality yields non-embeddable II$_1$ factors, giving a negative solution to Connes' embedding problem and to Tsirelson's problem.
  • The result rules out any effective classification of winnable tailored games: the promise problem that separates perfect ZPC value from low quantum value is RE-complete.
  • The compression theorem implies that any game below value 1/2 requires exponentially growing entanglement to be won with bounded probability, which is exactly what drives the fixed-point reduction.

Reading between the lines

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

  • A natural testable follow-up is to run the explicit transformations on a small tailored game such as the magic square game and check whether the perfect ZPC strategy survives compression; this would test the machinery at finite size.
  • Because the reduction is uniform in $M$, one could in principle search for non-sofic networks at a fixed finite scale by optimizing over the associated tailored games, though no practical algorithm is implied by the proof.
  • The tailored class may delimit how far proof-checking techniques can be combined with linear constraints: going further toward LCS games would require a new mechanism for encoding non-linear checks, which the paper leaves open.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper claims a negative resolution of the Aldous–Lyons conjecture (joint with the companion paper [BCLV24]) by proving TailoredMIP* = RE (Theorem 2.31): a polynomial-time map from Turing machines M to tailored non-local games G_M such that if M halts there is a perfect Z-aligned permutation strategy commuting along edges (ZPC), and if M never halts the synchronous quantum value is at most (claimed strictly less than) 1/2. The proof follows the MIP*=RE architecture: Section 2 derives Theorem 2.31 from a Compression Theorem (Theorem 2.53) by a fixed-point construction, and Compression is presented as the composition of question reduction, answer reduction, and parallel repetition, with proofs deferred to Sections 4–7. Section 3, included in the reviewed text, develops the technical toolbox: distances between strategies, data processing, a criterion for ZPC preservation (Corollary 3.41), game transformations, and the Pauli-basis self-test. The text under review contains Sections 1–3; the proofs of the three compression transformations are not present.

Significance. If the deferred proofs are correct, the result is of the first importance: it gives non-sofic unimodular networks (refuting Aldous–Lyons, via the reduction in [BCLV24]), reproves the negation of Connes' embedding problem (MIP*=RE) in a streamlined way, and establishes the stronger statement TailoredMIP* = RE with perfect strategies restricted to ZPC strategies. The visible portion is carefully written: the fixed-point construction and the deduction of Theorem 2.31 from Theorem 2.53 are explicit and mostly sound; Corollary 3.41 cleanly isolates the data-processing operations that preserve the tailored/ZPC category and is checkable from the material given; and the incorporation of simplifications from [dlS22b] and [Vid22] is a genuine strength. The significance is, however, conditional: the central technical contribution, a compression theorem that preserves the tailored structure, is asserted rather than proved in the reviewed text, and the paper itself identifies answer reduction as the delicate step. The present report therefore assesses the architecture and the visible deduction, not the full claim.

major comments (3)
  1. [§2.6.2 (Theorem 2.53); §5 (Theorem 5.1)] The main theorem is deduced from the Compression Theorem, but the proof of Compression is entirely deferred to Sections 4–7, which are not part of the text under review. The crux is Answer Reduction: as the introduction itself states in §1.1, the PCP must be designed so that "any bit of the encoded answer that depends on an unreadable bit of the original answer must do so in a linear manner only," and the proof of this property (Theorem 5.1) is not given. This is precisely the point at which the tailored setting departs from [JNV+21], where nonlinear dependence on answers is available, and it is load-bearing: if any encoded bit depended nonlinearly on unreadable bits, the completeness map via Corollary 3.41 would fail (the counterexample near (27) in §3.4 shows that the AND of two non-Z-aligned signed permutations is not a signed permutation), and the output game would not be tailored. The same concern applies to Question Reduction for conditionally linear samplers, stated as Theorem 4.36. A complete draft containing these proofs must be provided before the central claim can be verified.
  2. [§2.6.3, proof of Theorem 2.31 (completeness case)] The completeness argument contains a false inference: from n ≥ log N it concludes that 2n ≥ N, which is not true in general (e.g., if N = 2^10 and n = 10, then 2n = 20 < 1024). The correct threshold is N/2: from perfect ZPC strategies for V_{2n} with 2n ≥ N one obtains perfect ZPC strategies for V_n with n ≥ N/2, and iterating gives V_C after about log_2(N/C) halving steps. The iterated-logarithm chain in the text ("log N", "log log N", ...) is inconsistent with the factor-of-two index change in Theorem 2.53 and must be replaced by iterated halving. The conclusion is recoverable, but the proof as written is incorrect.
  3. [§2.6.3, Lemma 2.61] Lemma 2.61 is load-bearing: it is used to show both that V_{M,λ} is λ-bounded (so that Theorem 2.53 applies) and that the sampler and linear-constraints processor of G_M run in time poly(|M|). Its proof is only a sketch, ending with the suggestion that "it is probably better for the readers to try and follow these calculations for themselves," and the details are referred to [JNV+21, Lemma 12.5]. Since the present paper changes the verifier model (tailored normal form verifiers with a fixed canonical decider, and the specific fixed-point machine F of Definition 2.56), the revision should contain the full accounting argument rather than a pointer to the prior literature.
minor comments (5)
  1. [Theorem 2.31(3) and its proof] The soundness iteration establishes only E(V^{M,λ}_C, 1/2) = ∞, which implies val*(G_M) ≤ 1/2; the strict inequality claimed in Theorem 2.31(3) does not follow from this, because the supremum defining val* need not be attained by any finite-dimensional strategy. Theorem 1.1 and the informal definition of TailoredMIP* in §2.6 use the threshold ≤ 1/2; the statements should be aligned, or an additional argument for the strict inequality should be supplied.
  2. [Definition 2.56; Lemma 2.59(3); Corollary 2.60(1)] Definition 2.56 says F runs M for n steps and returns the empty tape if it halts, while Lemma 2.59(3) and Corollary 2.60(1) are phrased as "halts in less than n steps" and "halts in n steps"; these should consistently read "halts within n steps" to match the semantics of the machine F.
  3. [Claim 3.16] Claim 3.16 states that corners of PVMs are ε-almost projective, but the proof gives the slightly weaker bound (1 + 2ε)ε, since the deficiency bound τ(Id − ωω*) ≤ ε is taken with respect to the M-dimensional normalized trace while the 1-norm in the conclusion is N-dimensional. Subsequent uses absorb constants, so this is a precision issue rather than a substantive error, but the parameter should be adjusted.
  4. [Throughout] The manuscript contains numerous typos that a copyedit pass should fix: "proivde" in §1.2, "mononid" in Remark 1.3, "obejcts" in Remark 2.19, "sarisfied" and "constriants" in Example 2.29, "commonlu" in Definition 3.30, and "Scwhwartz" in the proof of Claim 3.18.
  5. [§2.6.3, displayed iteration in the proof of Theorem 2.31] The displayed chain of inequalities contains broken underbrace macros rendered literally as "bracehtipupleft/bracehtipdownright," which makes the chain difficult to read; the source should be repaired.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof proceeds through a self-contained compression theorem and a standard recursion-theoretic fixed point, with external citations providing independent support.

full rationale

The paper's derivation chain is not circular. Theorem 2.31 (TailoredMIP* = RE) is deduced from the Compression Theorem (2.53) by a standard fixed-point construction: the Turing machine F (Definition 2.56) implements the recursion theorem, producing a verifier V_{M,λ} that satisfies L_{M,λ}(...) = (L_{M,λ})'(...) when M does not halt in n steps (Remark 2.58, Lemma 2.59). This is a computational self-reference, not a logical assumption of the conclusion; the recursion theorem is an established external fact (cited to [Rog87]). The Compression Theorem is stated as a separate object, and the paper allocates Sections 4-7 to its proof; the proof is deferred but not circular. The adaptation of the MIP*=RE technique is presented as the paper's own contribution, with the bespoke PCP for answer reduction designed so that any bit depending on an unreadable original answer does so linearly; this is a claim backed by the proof in Section 5, and no equation reduces to an input parameter by construction. Reliance on [JNV+21], [dlS22b], [Vid22], and [BSGH+04] is to previously established, independent results (Vid22 is a self-citation but is an external publication with a proof idea included; it does not assume the paper's main theorem). The companion paper [BCLV24] is used only for the implication from Theorem 2.31 to non-sofic networks, not for the proof of Theorem 2.31. There are no fitted parameters, no predictions forced by definitions, and no ansatz smuggled in via citation.

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

The argument rests on standard mathematical facts and on the new definitional framework of tailored games. No free parameters are fitted to data. The paper introduces tailored games, ZPC strategies, and tailored normal form verifiers as formal definitions, not unexplained entities. The main domain-specific assumption is that compression can be performed while preserving the tailored structure, which the paper proves in later sections.

assumptions (4)
  • standard math Naimark's dilation theorem: every finite-dimensional POVM is a corner of a PVM.
    Used in Section 3.2 to relate partial POVMs to PVMs and to justify closeness arguments.
  • standard math The Pauli group P_k has a unique non-commuting irreducible representation, and the representation is stable (robust self-test).
    Used in Section 3.8 for the generalized Pauli basis game; stability from [dlS22b].
  • domain assumption The class of samplers is restricted to conditionally linear samplers (Definition 4.29).
    The compression theorem is proved for this class of samplers; the Halting reduction must keep games inside this class.
  • standard math The fixed-point construction from recursion theory can be applied to Turing machines.
    Used in Section 2.6.3 to define the halting tailored normal form verifier V_{M,lambda}.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Aldous--Lyons Conjecture II: Undecidability." pith.science (2026). https://pith.science/paper/2VED3PRP

@misc{pith2026250100173,
  author       = {Pith},
  title        = {Pith review of: The Aldous--Lyons Conjecture II: Undecidability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2VED3PRP}},
  note         = {Machine review of arXiv:2501.00173}
}
abstract

This paper, and its companion [BCLV24], are devoted to a negative resolution of the Aldous--Lyons Conjecture [AL07, Ald07]. In this part we study tailored non-local games. This is a subclass of non-local games -- combinatorial objects which model certain experiments in quantum mechanics, as well as interactive proofs in complexity theory. Our main result is that, given a tailored non-local game $G$, it is undecidable to distinguish between the case where $G$ has a special kind of perfect strategy, and the case where every strategy for $G$ is far from being perfect. Using a reduction introduced in the companion paper [BCLV24], this undecidability result implies a negative answer to the Aldous--Lyons conjecture. Namely, it implies the existence of unimodular networks that are non-sofic. To prove our result, we use a variant of the compression technique developed in MIP*=RE [JNV+21]. Our main technical contribution is to adapt this technique to the class of tailored non-local games. The main difficulty is in establishing answer reduction, which requires a very careful adaptation of existing techniques in the construction of probabilistically checkable proofs. As a byproduct, we are reproving the negation of Connes' embedding problem [Con76] -- i.e., the existence of a $\mathrm{II}_1$-factor which cannot be embedded in an ultrapower of the hyperfinite $\mathrm{II}_1$-factor -- first proved in [JNV+21], using an arguably more streamlined proof. In particular, we incorporate recent simplifications from the literature [dlS22b, Vid22] due to de la Salle and the third author.

Figures

Figures reproduced from arXiv: 2501.00173 by the authors.

Figure 1
Figure 1. In this figure there are 5 permutations, −Id, X⊗01 , X⊗10 , Z⊗01 , Z⊗10, acting on the set (F 2 2 )±. The X permutations act as bit flips. The Z permutations are conditional sign changes, namely, they flip the sign depending on whether the associated bit is 0 or 1. Finally, −Id flips the sign. does not halt then val∗ (GM) ≤ 1 2 . 24 The goal of this paper is to reprove this result with two extra conditions: The game… view at source ↗
Figure 2
Figure 2. This is an example of the actions of the Pauli matric [PITH_FULL_IMAGE:figures/full_fig_p059_2.png] view at source ↗
Figure 3
Figure 3. Questions and answers in the generalized Pauli bas [PITH_FULL_IMAGE:figures/full_fig_p061_3.png] view at source ↗
Figures from the paper (14 more)
Figure 4
Figure 4. Figure 4: The underlying graph of the commutation game [PITH_FULL_IMAGE:figures/full_fig_p062_4.png]
Figure 5
Figure 5. Figure 5: The underlying graph of the anti-commutation game [PITH_FULL_IMAGE:figures/full_fig_p063_5.png]
Figure 6
Figure 6. Figure 6: This is a partial picture of the underlying graph of [PITH_FULL_IMAGE:figures/full_fig_p065_6.png]
Figure 7
Figure 7. Figure 7: We list the main games, or transformations thereof [PITH_FULL_IMAGE:figures/full_fig_p069_7.png]
Figure 8
Figure 8. Figure 8: Questions and answers in the game Intro(G). Definition 4.2 (The introspection transformation of a tailored game). Let G be a (tailored) game with the above fixed proper￾ties. The introspection game Intro(G) consists of only two vertices IntroA and IntroB, with a single…
Figure 9
Figure 9. Figure 9: Questions and answers in the game Baby(G). Since the game is an augmentation of the sum of Pauli Basisk and Intro(G) we only list new questions and answers, and additional tests, and refer to [PITH_FULL_IMAGE:figures/full_fig_p074_9.png]
Figure 10
Figure 10. Figure 10: The underlying graph of Baby(G), where most of the embedded Pauli basis game is hidden. Question distribution of the baby question reduced game: With probability 1/4 do one of the following: • Sample an edge from Pauli Basisk according to the appropriate distribution …
Figure 11
Figure 11. Figure 11: An illustration of an h-level CLM s (adapted from [JNV+21, [PITH_FULL_IMAGE:figures/full_fig_p083_11.png]
Figure 12
Figure 12. Figure 12: Questions and answers in the game QueRedh(G, k, B). Since the game is an augmentation of the sum of Pauli Basisk (B) and Intro(G) we only list new questions and answers, and additional tests, and refer to [PITH_FULL_IMAGE:figures/full_fig_p088_12.png]
Figure 13
Figure 13. Figure 13: The underlying graph of QueRed(G), where most of the embedded Pauli basis game is hidden. Also, there are h − 2 extra vertices between Hide1 · and Hideh · . • The readable length of Hidej A (respectively Hidej B ) is k, and its unreadable length is k. We associate wit…
Figure 14
Figure 14. Figure 14: The type graph of QueRed(G). Though not drawn, all self loops are also edges in this type graph. So, in total, there are 2h + 28 vertices and 4h + 63 edges in this type graph. In this perspective, the vertices of QueRed(G) are from T × F m 2 × F m 2 . But the vertices…
Figure 15
Figure 15. Figure 15: An example of a circuit C with three input gates, a single output gate, and 15 wires. If we denote by Xi the formal variable associated with Inputi , then the polynomial the circuit induces at the single output vertex is PC (X1, X2, X3) = 1 + X1 + X2 + X3 + X1X2 + X1X…
Figure 16
Figure 16. Figure 16: Description of the low degree game LowDegree(d, q, m, k). be tailored by making all variables unreadable. Recall that q = 2 t , and using the basis from Fact 5.24, an element of Fq is encoded as a length-t bit string. • For Pointu , we set S L Pointu = {Pointu,i : i ∈…
Figure 17
Figure 17. Figure 17: The type graph of AnsRed(V, Λ, ∆, D, T, Q, n, t). Though not drawn, all self loops are also edges in this type graph. We added (five) colours that can be compared to the checks in the game. When the edge is either pink or green, Item (1), which is a low-degree test, i…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 56 canonical work pages

  1. [1]

    Computational complexity: a modern approach

    Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach . Cambridge University Press, 2009

    2009

  2. [2]

    On uniform hilbert schmidt stability of groups

    Danil Akhtiamov and Alon Dogon. On uniform hilbert schmidt stability of groups. Proceedings of the American Mathematical Society , 150(4):1799--1809, 2022

    work page 2022

  3. [3]

    Processes on Unimodular Random Networks

    David Aldous and Russell Lyons. Processes on Unimodular Random Networks . Electronic Journal of Probability , 12(none):1454 -- 1508, 2007

    work page 2007

  4. [4]

    Local weak limits and unimodularity

    David Aldous. Local weak limits and unimodularity. Blog post , 2007

    work page 2007

  5. [5]

    Combinatorial nullstellensatz

    Noga Alon. Combinatorial nullstellensatz. Combinatorics, Probability and Computing , 8(1-2):7--29, 1999

    work page 1999

  6. [6]

    A simple demonstration of B ell's theorem involving two observers and no probabilities or inequalities

    PK Aravind. A simple demonstration of B ell's theorem involving two observers and no probabilities or inequalities. arXiv preprint quant-ph/0206070 , 2002

    arXiv 2002

  7. [7]

    The Aldous--Lyons Conjecture I : Subgroup Tests

    Lewis Bowen, Michael Chapman, Alex Lubotzky, and Thomas Vidick. The Aldous--Lyons Conjecture I : Subgroup Tests . preprint , 2024

    work page 2024

  8. [8]

    On the einstein podolsky rosen paradox

    John S Bell. On the einstein podolsky rosen paradox. Physics Physique Fizika , 1(3):195, 1964

    1964

Show all 65 references
  1. [9]

    Non-deterministic exponential time has two-prover interactive protocols

    L \'a szl \'o Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. computational complexity , 1(1):3--40, 1991

    1991

  2. [10]

    Lifts, discrepancy and nearly optimal spectral gap

    Yonatan Bilu and Nathan Linial. Lifts, discrepancy and nearly optimal spectral gap. Combinatorica , 26(5):495--519, 2006

    2006

  3. [11]

    Operator algebras: theory of C*-algebras and von Neumann algebras , volume 122

    Bruce Blackadar. Operator algebras: theory of C*-algebras and von Neumann algebras , volume 122. Springer Science & Business Media, 2006

    2006

  4. [12]

    Invariant Means and Finite Representation Theory of C^* -Algebras , volume 13

    Nathanial Patrick Brown. Invariant Means and Finite Representation Theory of C^* -Algebras , volume 13. American Mathematical Soc., 2006

    2006

  5. [13]

    Robust pcps of proximity, shorter pcps and applications to coding

    Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. Robust pcps of proximity, shorter pcps and applications to coding. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , pages 1--10, 2004

    2004

  6. [14]

    Hardness amplification for entangled games via anchoring

    Mohammad Bavarian, Thomas Vidick, and Henry Yuen. Hardness amplification for entangled games via anchoring. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pages 303--316. ACM, 2017

    2017

  7. [15]

    Stability of homomorphisms, coverings and cocycles I : Equivalence

    Michael Chapman and Alex Lubotzky. Stability of homomorphisms, coverings and cocycles I : Equivalence . preprint , 2023

    2023

  8. [16]

    Perfect commuting-operator strategies for linear system games

    Richard Cleve, Li Liu, and William Slofstra. Perfect commuting-operator strategies for linear system games. Journal of Mathematical Physics , 58(1), 2017

    2017

  9. [17]

    Characterization of binary constraint system games

    Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. In International Colloquium on Automata, Languages, and Programming , pages 320--331. Springer, 2014

    2014

  10. [18]

    Classification of injective factors cases II_1 , II_ , III_ , 1

    Alain Connes. Classification of injective factors cases II_1 , II_ , III_ , 1 . Annals of Mathematics , pages 73--115, 1976

    1976

  11. [19]

    Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing , STOC '71, page 151–158, New York, NY, USA, 1971. Association for Computing Machinery

    1971

  12. [20]

    An algorithm for the machine calculation of complex Fourier series

    James W Cooley and John W Tukey. An algorithm for the machine calculation of complex Fourier series . Mathematics of computation , 19(90):297--301, 1965

    1965

  13. [21]

    Efficiently stable presentations from error-correcting codes

    Michael Chapman, Thomas Vidick, and Henry Yuen. Efficiently stable presentations from error-correcting codes. Preprint , 2023

    2023

  14. [22]

    Orthogonalization of Positive Operator Valued Measures

    Mikael de la Salle. Orthogonalization of Positive Operator Valued Measures . Comptes Rendus. Math\'ematique , 360:549--560, 2022

    2022

  15. [23]

    Spectral gap and stability for groups and non-local games, 2022

    Mikael de la Salle. Spectral gap and stability for groups and non-local games, 2022

    2022

  16. [24]

    o ttingen: K \

    CF Gauss. Theoria interpolationis methodo nova tractata werke band 3, 265--327. G \"o ttingen: K \"o nigliche Gesellschaft der Wissenschaften , 1886

  17. [25]

    Gowers and Omid Hatami

    William T. Gowers and Omid Hatami. Inverse and stability theorems for approximate representations of finite groups. Mat. Sb. , 208(12):70--106, 2017

    2017

  18. [26]

    A history of the PCP Theorem

    Venkatesan Guruswami and Ryan O'Donnell. A history of the PCP Theorem . https://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf , 2005

    2005

  19. [27]

    o del. \

    Kurt G \"o del. \"U ber formal unentscheidbare s \"a tze der principia mathematica und verwandter systeme i. Monatshefte f \"u r mathematik und physik , 38:173--198, 1931

    1931

  20. [28]

    Almost solutions of equations in permutations

    Lev Glebsky and Luis Manuel Rivera. Almost solutions of equations in permutations. Taiwanese J. Math. , 13(2A):493--500, 2009

    2009

  21. [29]

    Loophole-free bell inequality violation using electron spins separated by 1.3 kilometres

    Bas Hensen, Hannes Bernien, Ana \" s E Dr \'e au, Andreas Reiserer, Norbert Kalb, Machiel S Blok, Just Ruitenberg, Raymond FL Vermeulen, Raymond N Schouten, Carlos Abell \'a n, et al. Loophole-free bell inequality violation using electron spins separated by 1.3 kilometres. Nat...

    2015

  22. [30]

    Expander graphs and their applications

    Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. , 43:439--561, 2006

    2006

  23. [31]

    Hopcroft, Rajeev Motwani, and Jeffrey D

    John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition) . Addison-Wesley Longman Publishing Co., Inc., USA, 2006

    2006

  24. [32]

    Stability of group relations under small H ilbert- S chmidt perturbations

    Don Hadwin and Tatiana Shulman. Stability of group relations under small H ilbert- S chmidt perturbations. J. Funct. Anal. , 275(4):761--792, 2018

    2018

  25. [33]

    Stability for product groups and property ( )

    Adrian Ioana. Stability for product groups and property ( )

  26. [34]

    Quantum soundness of the classical low individual degree test

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

    2009 arXiv

  27. [35]

    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP*=RE . Commun. ACM , 64(11):131--138, 2021

    2021

  28. [36]

    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. IEEE, 2022

    2021

  29. [37]

    Quantum soundness of testing tensor codes

    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. Quantum soundness of testing tensor codes. Discrete Analysis , 12 2022

    2022

  30. [38]

    Class of constructive asymptotically good algebraic codes

    J rn Justesen. Class of constructive asymptotically good algebraic codes. IEEE Transactions on information theory , 18(5):652--656, 1972

    1972

  31. [39]

    Richard M. Karp. Reducibility among Combinatorial Problems , pages 85--103. Springer US, Boston, MA, 1972

    1972

  32. [40]

    A synchronous game for binary constraint systems

    Se-Jin Kim, Vern Paulsen, and Christopher Schafhauser. A synchronous game for binary constraint systems. Journal of Mathematical Physics , 59(3):032201, 2018

    2018

  33. [41]

    Universal sequential search problems

    Leonid Anatolevich Levin. Universal sequential search problems. Problemy peredachi informatsii , 9(3):115--116, 1973

    1973

  34. [42]

    Algebraic methods for interactive proof systems

    Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. In Proceedings of 31st Annual Symposium on Foundations of Computer Science , pages 2--10. IEEE, 1990

    1990

  35. [43]

    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 , pages 1--11, 2022

    2022

  36. [44]

    Products of synchronous games

    L Man c inska, VI Paulsen, IG Todorov, and A Winter. Products of synchronous games. Studia Mathematica , 272:299--317, 2023

    2023

  37. [45]

    The recursive compression method for proving undecidability results

    Andrew Marks, Seyed Sajjad Nezhadi, and Henry Yuen. The recursive compression method for proving undecidability results. Manuscript , 2024

    2024

  38. [46]

    A quantum linearity test for robustly verifying entanglement

    Anand Natarajan and Thomas Vidick. A quantum linearity test for robustly verifying entanglement. In S TOC '17--- P roceedings of the 49th A nnual ACM SIGACT S ymposium on T heory of C omputing , pages 1003--1015. ACM, New York, 2017

    2017

  39. [47]

    Low-degree testing for quantum states, and a quantum entangled games PCP for QMA

    Anand Natarajan and Thomas Vidick. Low-degree testing for quantum states, and a quantum entangled games PCP for QMA . In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pages 731--742. IEEE, 2018

    2018

  40. [48]

    Two-player entangled games are NP-hard

    Anand Natarajan and Thomas Vidick. Two-player entangled games are NP-hard . In Proceedings of the 33rd Computational Complexity Conference , page 20. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018

    2018

  41. [49]

    NEEXP is contained in MIP*

    Anand Natarajan and John Wright. NEEXP is contained in MIP* . In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) , pages 510--518. IEEE, 2019

    2019

  42. [50]

    Completely Bounded Maps and Operator Algebras

    Vern Paulsen. Completely Bounded Maps and Operator Algebras . Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2003

    2003

  43. [51]

    Nearly-linear size holographic proofs

    Alexander Polishchuk and Daniel A Spielman. Nearly-linear size holographic proofs. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing , pages 194--203, 1994

    1994

  44. [52]

    Satisfiability problems and algebras of boolean constraint system games

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

    2023 arXiv

  45. [53]

    Estimating quantum chromatic numbers

    Vern I Paulsen, Simone Severini, Daniel Stahlke, Ivan G Todorov, and Andreas Winter. Estimating quantum chromatic numbers. Journal of Functional Analysis , 270(6):2188--2222, 2016

    2016

  46. [54]

    A parallel repetition theorem

    Ran Raz. A parallel repetition theorem. In Proceedings of the twenty-seventh annual ACM symposium on Theory of computing , pages 447--456, 1995

    1995

  47. [55]

    Theory of Recursive Functions and Effective Computability

    Hartley Rogers, Jr. Theory of Recursive Functions and Effective Computability . MIT Press , Cambridge, MA, USA , 1987

    1987

  48. [56]

    Robust characterizations of polynomials with applications to program testing

    Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing , 25(2):252--271, 1996

    1996

  49. [57]

    Fast probabilistic algorithms for verification of polynomial identities

    Jacob T Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM (JACM) , 27(4):701--717, 1980

    1980

  50. [58]

    IP = PSPACE

    Adi Shamir. IP = PSPACE . In Proceedings of 31st Annual Symposium on Foundations of Computer Science , pages 11--15. IEEE, 1990

    1990

  51. [59]

    Introduction to the T heory of C omputation

    Michael Sipser. Introduction to the T heory of C omputation . Cengage L earning, 2012

    2012

  52. [60]

    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 , 2019

    2019

  53. [61]

    Bell inequalities and operator algebras, 2006

    Boris S Tsirelson. Bell inequalities and operator algebras, 2006. Problem statement from website of open problems at TU Braunschweig (2006), available at http://web.archive.org/web/20090414083019/http://www.imaph.tu-bs.de/qi/problems/33.html

    2006

  54. [62]

    Alan M. Turing. On computable numbers, with an application to the E ntscheidungsproblem. Proceedings of the London mathematical society , 2(1):230--265, 1937

    1937

  55. [63]

    Almost synchronous quantum correlations

    Thomas Vidick. Almost synchronous quantum correlations. Journal of mathematical physics , 63(2), 2022

    2022

  56. [64]

    Probabilistic algorithms for sparse polynomials

    Richard Zippel. Probabilistic algorithms for sparse polynomials. In International symposium on symbolic and algebraic manipulation , pages 216--226. Springer, 1979

    1979

  57. [65]

    Property (T) and Kazhdan constants for discrete groups

    Andrzej \.Z uk. Property (T) and Kazhdan constants for discrete groups . Geometric & Functional Analysis GAFA , 13:643--670, 2003

    2003

Pith tools

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