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
| CREATOR | Lewis Bowen, Michael Chapman, Thomas Vidick |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 921 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-00173