The Aldous--Lyons Conjecture II: Undecidability

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 II₁-factor which cannot be embedded in an ultrapower of the hyperfinite II₁-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.