Inapproximability through undecidability (Thomas VIDICK, EPFL)

23.04.2026 16:15

Infinite combinatorial, algebraic or other structures, such as a graph, a group, or a probability space, can sometimes be approximated (in a suitable sense) by finite structures, and sometimes not. In the former case, finite approximability can provide a convenient proxy for studying the infinite structure; in the latter, inapproximability underscores a genuinely distinct behavior from the finite case. While the existence of finite approximations can follow from suitable approximation techniques, their in-existence often requires deeper conceptual observations.

Recently we were able to resolve some long-standing inapproximability questions, in algebra and in ergodic theory, by showing that an associated computational problem is undecidable. Associating a measure of complexity to the infinite structure allows us to make use of methods from complexity theory and demonstrate the in-existence of finite approximations in an unexpected way.

In the talk we will discuss this "method" and show how we used it to answer the Connes Embedding Problem, about the existence of inapproximable classes of (type II_1) von Neumann algebras, and the Aldous-Lyons conjecture, about the existence of inapproximable (unimodular) infinite graphs.

Based on joint works with Ji, Natarajan, Yuen and Wright, and Bowen, Chapman and Lubotzky.

Le colloque sera suivi d'un apéritif

Lieu

Bâtiment: Conseil Général 7-9

Salle 1-15, Colloque de mathématiques

entrée libre

Fichiers joints

Colloque Thomas Vidick .pdf

68.3 Kb