COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |
University of Cambridge > Talks.cam > Geometric Group Theory (GGT) Seminar > Subgroup Tests and the Aldous-Lyons conjecture
Subgroup Tests and the Aldous-Lyons conjectureAdd to your list(s) Download to your calendar using vCal
If you have a question about this talk, please contact Francesco Fournier-Facio. Joint seminar: GGT - Discrete Analysis - 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 Geometric Group Theory (GGT) Seminar series. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsImagine 2017 BP Lectures 2011 Mini Courses in Theoretical Computer ScienceOther talksCelestial symmetries charges at null infinity from twistor space Proofs on Inductive Predicates in Why3 Dynamical decoupling of open quantum systems Phase Transition and Ergodicity Breaking During Avian Foraging Group Presentation 3 Hyper-Lagrangians and Joyce structures |