Subgroup tests and the Aldous-Lyons conjecture

Add to your list(s) Download to your calendar using vCal

• Michael Chapman (NYU)
• Wednesday 13 November 2024, 13:30-15:00
• MR4, CMS.

If you have a question about this talk, please contact Julia Wolf.

Joint seminar: Discrete Analysis - Geometric Group Theory - Combinatorics - Quantum Computing - Algorithms and Complexity

The Aldous-Lyons conjecture from probability theory states that every (unimodular) infinite graph can be (Benjamini-Schramm) approximated by finite graphs. This conjecture is an analogue of other influential conjectures in mathematics concerning how well certain infinite objects can be approximated by finite ones; examples include Connes’ embedding problem (CEP) in functional analysis and the soficity problem of Gromov-Weiss in group theory. These became major open problems in their respective fields, as many other long standing open problems, that seem unrelated to any approximation property, were shown to be true for the class of finitely-approximated objects. For example, Gottschalk’s conjecture and Kaplansky’s direct finiteness conjecture are known to be true for sofic groups, but are still wide open for general groups.

In 2019, Ji, Natarajan, Vidick, Wright and Yuen resolved CEP in the negative. Quite remarkably, their result is deduced from complexity theory, and specifically from undecidability in certain quantum interactive proof systems. Inspired by their work, we suggest a novel interactive proof system which is related to the Aldous-Lyons conjecture in the following way: If the Aldous-Lyons conjecture was true, then every language in this interactive proof system is decidable. A key concept we introduce for this purpose is that of a Subgroup Test, which is our analogue of a Non-local Game. By providing a reduction from the Halting Problem to this new proof system, we refute the Aldous-Lyons conjecture.

This talk is based on joint work with Lewis Bowen, Alex Lubotzky, and Thomas Vidick. No special background in probability theory or complexity theory will be assumed.

This talk is part of the Discrete Analysis Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Department of Computer Science and Technology talks and seminars
• Discrete Analysis Seminar
• Hanchen DaDaDash
• Interested Talks
• MR4, CMS
• Quantum Computing Seminar
• School of Physical Sciences
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.