The Aldous–Lyons Conjecture II: Undecidability

Lewis Bowen, Michael Chapman, Thomas Vidick · 2025

Read The Aldous–Lyons Conjecture II: Undecidability by Lewis Bowen, Michael Chapman, Thomas Vidick (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00173.txt.

Description

Lewis Bowen and co-authors published a research paper in 2024 proving that a long-standing conjecture about networks is false, by way of an undecidability result. The conjecture asked whether every symmetric random network can be approximated by finite ones. The team attacks a tailored class of nonlocal games, puzzles that also model quantum experiments and proof systems.

They show no algorithm can tell whether such a game admits a perfect play of a special kind or whether every play falls far short. A bridge built in their companion paper turns that undecidability into a counterexample network. As a side result, the proof again settles a famous embedding problem from operator algebras.

Catalog record

CREATORLewis Bowen, Michael Chapman, Thomas Vidick
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE921 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-00173

Browse the full library · About the Tower of Babel