The Aldous--Lyons Conjecture II: Undecidability

• URL: http://arxiv.org/abs/2501.00173v1
• Date: Mon, 30 Dec 2024 22:59:56 GMT
• Title: The Aldous--Lyons Conjecture II: Undecidability
• Abstract summary: We show 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.<n>Using a reduction introduced in the companion paper [BCLV24], this undecidability result implies a negative answer to the Aldous--Lyons conjecture.
• Score: 3.8370118222043694
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Auditing an AI-Generated Mathematical Proof: A Correction to a Greedy Conditioning Lemma in Quantum Parallel Repetition [0.0]
  This note gives an explicit counterexample, identifies the intended continuation condition, and supplies a complete corrected proof.<n>It should not, however, be read as an independent verification of the main parallel-repetition theorem.
  arXiv  Detail & Related papers  (2026-08-03T15:12:46Z)
• Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials [2.5782420501870296]
  We show that for any constant $s$ there exists an $s$-server private information retrieval protocol.<n>Our number-theoretic conjecture is implied by existing conjectures.
  arXiv  Detail & Related papers  (2026-07-24T06:59:30Z)
• Odds Law: The Decomposition Algebra On How Intelligence Organizes Itself to Solve Difficult Problems Reliably [0.5414847001704247]
  We show that reliability is bought with independent information arranged by composition, and bounded by the verifier.<n>In short, reliability is neither free nor magical: it is bought with independent information, arranged by composition, and bounded by the verifier.
  arXiv  Detail & Related papers  (2026-06-14T09:53:11Z)
• Yanasse: Finding New Proofs from Deep Vision's Analogies, Part 1 [51.56484100374058]
  System extracts tactic usage distributions across 27 top-level areas of Mathlib.<n>It computes z-scores to identify tactics that are heavily used in a source area but rare or absent in a target area.<n>It matches source and target proof states via GPU-accelerated NP-hard analogy.
  arXiv  Detail & Related papers  (2026-04-19T03:27:16Z)
• Choices and their Provenance: Explaining Stable Solutions of Abstract Argumentation Frameworks [1.4064491732635236]
  We present a novel approach for extending this provenance to stable AF solutions.<n>Our approach identifies minimal sets of critical attacks, pinpointing choices and assumptions made by a stable model.
  arXiv  Detail & Related papers  (2025-06-01T17:09:55Z)
• Cloning Games, Black Holes and Cryptography [53.93687166730726]
  We introduce a new toolkit for analyzing cloning games. These games capture more quantitative versions of no-cloning and are central to unclonable cryptography.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
  Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also found applications in differential privacy, mildly, and quantum learning theory.
  arXiv  Detail & Related papers  (2024-09-17T23:09:25Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
  arXiv  Detail & Related papers  (2024-08-27T18:28:31Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Efficiently stable presentations from error-correcting codes [5.69361786082969]
  We provide a general method for constructing presentations of $mathbbZk$ from linear error-correcting codes. We observe that the resulting presentation has a weak form of stability exactly when the code is emphtestable. While we cannot show that this is the case in general, we leverage recent results in the study of non-local games in quantum information theory.
  arXiv  Detail & Related papers  (2023-11-08T13:40:13Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  We show that our algorithm achieves an $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ are the cardinalities of the state and action spaces
  arXiv  Detail & Related papers  (2023-05-15T05:37:32Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  We show that the Connes embedding problem implies the synchronous Tsirelson conjecture. We also give a different construction of Connes' algebra $mathcalRomega$ appearing in the Connes embedding problem.
  arXiv  Detail & Related papers  (2022-09-16T13:59:42Z)
• Agnostic Online Learning and Excellent Sets [21.87574015264402]
  We prove existence of large indivisible'' sets in $k$-edge stable graphs. A theme in these proofs is the interaction of two abstract notions of majority, arising from measure, and from rank or dimension.
  arXiv  Detail & Related papers  (2021-08-12T07:33:33Z)
• A monogamy-of-entanglement game for subspace coset states [7.716156977428555]
  This property was conjectured recently by [Coladangelo, Liu, Liu, and Zhandry, Crypto'21] and shown to have applications to unclocrypt decryption and copy-protection of pseudorandom functions. We present two proofs, one which directly follows the method of the original paper and the other which uses an observation from [Vidick and Zhang, Euro'20] to reduce the analysis to a simpler monogamy game based on BB'84 states.
  arXiv  Detail & Related papers  (2021-07-28T12:41:39Z)
• MIP*=RE [9.42581332803306]
  We show that the class MIP* of languages can be decided by a classical verifier interacting with multiple quantum provers sharing entanglement. We provide a refutation of Connes' theory of von Neumann algebras.
  arXiv  Detail & Related papers  (2020-01-13T16:32:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.