Recursion Theory/Descriptive Set Theory Seminar - Fall 2024

---

Time: Fridays 11:00-12:30
Location: 736 Evans

Topic:Hyperfiniteness, asymptotic dimension, and Borel geometry of countable Borel equivalence relations.

Tentative Schedule:

• Jan 31, Feb 7: Introduction to hyperfiniteness (Yvette/Daniel):
  • Dougherty, Jackson, Kechris (1994) The structure of hyperfinite Borel equivalence relations.
  • Kechris, Miller (2004) Topics in orbit equivalence.
• Feb 14, 21: Hyperfiniteness of Z^n actions, asymptotic cones, and toast (David/Katalin)
  • Boykin, Jackson (2007) Borel boundedness and the lattice rounding property
  • Marks, Unger (2017) Borel circle squaring
• Feb 28: Introduction to asymptotic dimension (Liza):
  • Bell, Dranishnikov (2008) Asymptotic Dimension
• Mar 7, 14: Borel asymptotic dimension and hyperfiniteness (Alex T./Yiping):
  • Conley, Jackson, Marks, Seward, Tucker-Drob (2023) Borel asymptotic dimension and hyperfiniteness.
• Mar 21: Hyperfiniteness of Borel graphs of polynomial growth (Alex K./Felix):
  • Bernshteyn, Yu (2023) Large-Scale Geometry of Borel graphs of polynomial growth.
• Apr 4: Slawek Solecki: The projective amalgamation property of simplicial maps.
• Apr 11: Hyperfiniteness of Borel graphs of slow intermediate growth (Alex K./Felix):
  • Grebík, Marks, Rozhoň, Shinko (2025) Hyperfiniteness of Borel graphs of slow intermediate growth.
• Apr 18: Pieter Spaas: Reductions from synchronous nonlocal games to independent set games
  
  Abstract: We will discuss nonlocal games, in particular independent set games on graphs, and quantum strategies for them. We will then describe a reduction from general synchronous games to independent set games. This was first done for perfect strategies by Mančinska, Roberson, and Varvitsiotis, and we will show how to lift this result to approximate strategies. This yields a so-called gap-preserving reduction, with further implications towards the complexity of deciding (the gapped promise problem for) the quantum value of independent set games. The proof of this result also requires a new stability theorem for rounding approximate PVMs to genuine PVMs. We will introduce the necessary background, and discuss these results as well as the main ideas behind their proofs. This talk is based on joint work with Laura Mančinska and Taro Spirig.
• Apr 25: Dino Rossegger?: TBA
• May 2: Borel combinatorics, asymptotic dimension, and asymptotic separation index (Cecelia/Forte):
  • Qian, Weilacher (2024) Descriptive combinatorics, computable combinatorics, and asi algorithms
  • Weilacher, Bernshteyn (2024) Borel versions of the Local Lemma and LOCAL algorithms for graphs of finite asymptotic separation index.