McGill

Descriptive Dynamics and Combinatorics

Seminar

Organizers: Ruiyuan (Ronnie) Chen, Marcin Sabok, & Anush Tserunyan
Typical time (unless specified otherwise below): Tuesday at 15:40 ET (50 minutes + ε)
Online location: Zoom meeting https://mcgill.zoom.us/j/87587975637, password: Bor▩▩ (the σ-algebra generated by open sets)
Physical location: Burnside 920

Regular seminar is on pause until September (2022), however occasional talks may be given before then.



Past talks

2022 Apr 26 Speaker: Jenna Zomback (University of Illinois Urbana-Champaign)
Title: Gaboriau's fundamental theorem of cost
Abstract

In order to distinguish countable Borel equivalence relations (CBERs) up to measure isomorphism, Gilbert Levitt introduced an invariant called cost. I will present my understanding of Damien Gaboriau's "Mercuriale de groupes et de relations", which shows that any Borel treeing of a CBER achieves its cost. In particular, the cost of a free, ergodic, pmp action of the free group on n generators is n.

Notes and recording
2022 Apr 19 Speaker: Antoine Poulin (McGill University)
Title: Complexity of Archimedean orders
Abstract

Orderings on groups have been studied from many angles. Such orders can be encoded into a Polish space, and the Borel complexity of isomorphisms of orders has been a recent subject of study. Motivated by a question of Calderoni, Marker, Motto Ros and Shani, we prove that the isomorphism relation on Archimedean orders of ℤ​2 is hyperfinite, but not smooth.

Slides
2022 Apr 12 Speaker: Aristotelis Panagiotopoulos (Carnegie Mellon University)
Title: Strong ergodicity phenomena for Bernoulli shifts of bounded algebraic dimension
Abstract

For every Polish permutation group P≤Sym(ℕ) let A↦[A]P be the assignment which maps every A⊆ℕ to the set of all k ∈ ℕ whose orbit under the action of the stabilizer PA of A is finite. Then A↦[A]P is a closure operator and hence it endows P with a natural notion of dimension dim(P). This notion of dimension has been extensively studied in model theory when A↦[A]P satisfies additionally the exchange principle; that is, when A↦[A]P forms a pregeometry. However, under the exchange principle every Polish permutation group P with dim(P)<∞ is locally compact and therefore unable to generate any "wild" dynamics. In this talk we will discuss the relationship between dim(P) and certain strong ergodicity phenomena in the absence of the exchange principle. In particular, for every n ∈ ℕ  we will provide a Polish permutation group P with dim(P)=n whose Bernoulli shift P↷ℝ is generically ergodic relative to the injective part of the Bernoulli shift of any permutation group with dim(Q)<n. We will use this to exhibit an equivalence relation of pinned cardinal ℵ1 which strongly resembles Zapletal’s counterexample to a question of Kechris, but which does not Borel reduce to the latter. Our proofs rely on the theory of symmetric models of choiceless set-theory and in the process we establish that a vast collection of symmetric models admit a theory of supports similar to the basic Cohen model. This is joint work with Assaf Shani.

Slides
2022 Apr 5 Speaker: Ádám Timár (University of Iceland and Rényi Institute)
Title: Poisson matchings of optimal tail via matchings in graphings
Abstract

Consider the following purely probabilistic problem. Take two infinite random discrete sets of points in the Euclidean space whose distributions are invariant under isometries. Find a "factor" perfect matching between the two, where factor means, intuitively, that every point can determine its pair using local information and using the same method. We want to make the probability that some fixed point is at distance at least r from its pair decay as fast as possible. A recent result of Bowen, Kun, and Sabok has become an important tool in settling this question for Poisson point processes, where we found a construction with optimal tail, significantly improving on previous ones.

Slides
2022 Mar 22 Speakers: Thomas Buffard, Gabriel Levrel, Sam Mayo (McGill University)
Title: Borel determinacy in 50 (+ε) minutes
Abstract

Borel determinacy asserts that any two-player game of perfect information with a Borel payoff set is determined. The theorem was proved by Donald Martin in 1975, and while it holds much importance across descriptive set theory, its proof is technically difficult. In this talk we will outline the main ideas of the proof, including background on infinite games and determinacy. If time permits we will discuss the details of Martin’s most recent simplification of the proof using taboos, which we streamlined.

Annotated slides
2022 Mar 15 Speaker: Ruiyuan (Ronnie) Chen (CRM / McGill University)
Title: Introduction to Poisson processes
Abstract

The Poisson process provides a canonical way to build a probability space from a possibly infinite measure space. We give an introduction to Poisson processes from a descriptive set theorist's perspective, with some applications to constructing free pmp actions of Polish groups.

Notes
2022 Mar 8 Speaker: Julien Melleray (Université Lyon 1)
Title: Generic properties of (chain-transitive) homeomorphisms preserving a given dynamical simplex
Abstract

Given a set K of Borel probability measures on the Cantor space X, consider the set GK of all homeomorphisms which preserve every measure in K and which do not fix any nontrivial clopen set. For some Bernoulli measures µ, A. Yingst proved that the set of invariant measures of a generic element of Gµ is as small as possible (equal to {µ} in certain cases; this gives many interesting examples of totally ergodic homeomorphisms). I will explain why Yingst's result is a particular case of a theorem about dynamical simplices, i.e. sets of invariant measures of minimal homeomorphisms. I will recall the characterization of a dynamical simplex, try to motivate their study and the problem at hand; if time permits I will describe another Baire-category fact (describing when their exist nonmeager conjugacy classes in GK) and why it rules out a potential approach towards computing the Borel complexity of conjugacy of minimal homeomorphisms (a well-known open problem).

Annotated slides
2022 Feb 22 Speaker: Jenna Zomback (University of Illinois Urbana-Champaign)
Title: Pointwise ergodic theorems for semigroup actions
Abstract

We discuss new pointwise ergodic theorems for free semigroup actions, where the averages are taken over trees. This is joint work with Anush Tserunyan.

Annotated slides and recording
2022 Feb 15 Speaker: Sam Mellick (ENS de Lyon)
Title: Visualising actions, computing cost, and fixed price for G x Z
Abstract

Actions of locally compact groups can be profitably studied by looking at their lacunary sections. In particular, lacunary sections can be used to define the cost of essentially free pmp actions of such groups.

In this talk, I will explain how you can visualise a lacunary section as an "invariant point process" on the group, and I will show how this picture can be exploited to give the first new technique for computing the cost of actions of nondiscrete groups.

No knowledge of probability theory will be required.

Joint work with Miklós Abért.

Slides
2022 Feb 8 Speaker: Konrad Wrobel (Steklov Math. Institute at St. Petersbourg)
Title: Orbit equivalence, cofinitely equivariant maps, and wreath products
Abstract

We prove various antirigidity and rigidity results around the orbit equivalence of wreath product actions. Let F be a nonabelian free group. In particular, we show that the wreath products $A \wr F$ and $B \wr F$ are orbit equivalent for any pair of nontrivial amenable (possibly finite) groups A, B. This is most interesting when the group A is finite. In order to accomplish this, we introduce the notion of a cofinitely equivariant map between shift spaces. This is joint work with Robin Tucker-Drob.

Notes
2022 Feb 1 Speaker: Matthew Bowen (McGill University)
Title: One-ended spanning trees and generic combinatorics
Abstract

We show that every one-ended bounded degree Borel graph admits a one-ended component spanning tree on a comeagre Borel set. As an application, we show that such graphs admit Borel perfect matchings generically if they are bipartite and d-regular, and admit balanced orientations generically if they are 2d-regular. This talk is based on upcoming work with Poulin and Zomback.

Slides
2021 Dec 13 Speaker: Colin Jahel (Carnegie Mellon University)
Title: Invariant random subgroups of Polish groups (with a focus on S)
Abstract

(This is a work in progress with Matthieu Joseph.) The notion of invariant random subgroups (IRS) classically describes the conjugacy invariant measures on the (compact) space of closed subgroups of a given locally compact group. Our idea is to explore this notion when working with a Polish group instead of a locally compact one. In particular, the permutation group of the integers, S, is a very rich example of a Polish group that yields interesting results when it comes to IRSs. I will define all the notions mentioned in this abstract, spending in particular some time to describe subgroups of S.

Notes
2021 Dec 6 Speaker: Forte Shinko (Caltech)
Title: Lifts of Borel actions on quotient spaces
Abstract

Given a countable Borel equivalence relation E, we consider the problem of lifting a Borel action of a countable group Gamma on X/E to a Borel action of Gamma on X. This is always possible when E is compressible, but it can happen that there are Borel bijections of X/E which do not lift to Borel automorphisms of E. This leads us to consider the problem of lifting outer actions, that is, actions on X/E induced by Borel automorphisms of E. We show that for many classes of groups Gamma, such as amenable groups and amalgamated products of finite groups, it is possible to lift any outer action on any X/E, and we show that any such group must be treeable. This is joint work with Joshua Frisch and Alexander Kechris.

Slides
2021 Nov 29 Speaker: Zoltán Vidnyánszky (Caltech)
Title: Determinacy, measure, toasts, and the shift graph
Abstract

We establish several new complexity results using the shift graph on [ℕ]​​:

  1. Using measure theory and graphs with large expansion, we show that there it is hard to decide the Borel chromatic number of locally finite, acyclic, bounded degree graphs.
  2. Using determinacy and Marks' method, we prove the optimal result in the Borel context.
  3. Using toasts, we show a Borel analogue of the Hell-Nesetril theorem.

Annotated slides
2021 Nov 15 Speaker: Filippo Calderoni (University of Illinois Chicago)
Title: Rotation equivalence
Abstract

In this talk we will present some results about the Euclidean spheres in higher dimensions and the corresponding orbit equivalence relations induced by the group of rational rotations. We will show that such equivalence relations are not treeable in dimension greater than 2. Also we will discuss progress on the conjecture that such equivalence relation are not universal CBERs.

2021 Nov 8 Speaker: Jan Grebik (University of Warwick)
Title: Homomorphism graphs and Descriptive combinatorics
Abstract

I will introduce a new type of Borel graphs, homomorphism graphs, and show how to extend the celebrated determinacy method of Marks to these graphs. The main idea, rather surprisingly, comes from the adaptation of Marks' technique to the LOCAL model of distributed computing. In the talk, I will discuss this adaptation as well as some applications of this approach in descriptive combinatorics.
This is a joint work with Brandt, Chang, Grunau, Rozhoň and Vidnyánszky.

Slides
2021 Nov 1 Speaker: Matthew Bowen (McGill University)
Title: Measurable integral flows and perfect matchings in hyperfinite graphings
Abstract

In this talk I will discuss problems related to finding measurable integral flows and perfect matching in hyperfinite graphings (probability measure preserving Borel graphs), as well as applications to measurable equideompositions. In particular, I will show that for one ended hyperfinite graphings, admitting a measurable integral flow is equivalent to admitting a (not necessarily measurable) flow, and that such graphings also admit measurable perfect matchings if they are bipartite and d-regular. These results will then be applied to give new proofs of measurable circle squaring. Based on joint work with Marcin Sabok and Gábor Kun.

Annotated slides
2021 Oct 25 Speaker: Ruiyuan (Ronnie) Chen (CRM / McGill University)
Title: A representation theorem for cardinal algebras
Abstract

Tarski's 1949 theory of cardinal algebras seeks to axiomatize key features of cardinal arithmetic without assuming the axiom of choice. The theory is remarkable in its efficiency: from a few simple axioms, Tarski (and later authors) derive seemingly all conceivable "natural" properties of countable addition in familiar algebras such as [0,∞]. In this talk, I will present a result that partly explains this phenomenon: every cardinal algebra A embeds into an algebra of Borel [0,∞]-valued functions (on a standard Borel space when A is countably presented, and more generally on a locale). As an application, I will sketch an abstract, nearly combinatorics-free proof of Nadkarni's theorem on the existence of invariant measures.

Annotated slides
2021 Oct 18 Speaker: Dakota Ihli (University of Illinois Urbana-Champaign / McGill University)
Title: Genericity of absolutely continuous interval homeomorphisms, part 2: proofs
Abstract

We present a new result, namely that the group of absolutely continuous homeomorphisms of the interval admits a comeagre conjugacy class (i.e. it admits generic elements). Furthermore, we give a characterization of the generic elements.

Notes
2021 Oct 4 Speaker: Dakota Ihli (University of Illinois Urbana-Champaign / McGill University)
Title: Genericity of absolutely continuous interval homeomorphisms, part 1: introduction
Abstract

We present a new result, namely that the group of absolutely continuous homeomorphisms of the interval admits a comeagre conjugacy class (i.e. it admits generic elements). Furthermore, we give a characterization of the generic elements.

Notes
2021 Aug 6 Speaker: Dakota Ihli (University of Illinois Urbana-Champaign)
Title: The group of absolutely continuous homeomorphisms of [0,1] is topologically 2-generated
Abstract

Akhmedov and Cohen recently showed that the homeomorphism group of the interval is generically 2-generated ¶mdash; that is, the generic pair of elements generate a dense subgroup. In this talk we outline the proof of this result, and we show how it may be altered to show the same result for the group of absolutely continuous homeomorphisms of the interval.

Notes
2021 Jul 20 Speaker: Marcin Sabok (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 8
Abstract

In this part, we finish covering Section 3 of the paper of Conley, Gaboriau, Marks and Tucker-Drob. We will discuss the proof of the fact that any Borel planar graph is measure treeable.

Notes
2021 Jul 9 Speaker: Marcin Sabok (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 7
Abstract

In this part, we cover the first part of Section 3 of the paper of Conley, Gaboriau, Marks and Tucker-Drob. We will discuss the proof of the fact that any Borel planar graph is measure treeable.

Notes
2021 Jul 2 Speaker: Anush Tserunyan (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 6: local-global bridges, 2-ended graphs, and
the 1% lemma
Abstract

We will begin the talk by explicitly stating and explaining the local-global bridge lemmas in the pmp setting that were used in various constructions, e.g. to go from nowhere µ-hyperfiniteness to exponential growth. We then discuss properties of 2-ended graphs, maximal hyperfinite connected subrelations, and prove the 1% lemma — a conservation property for µ-nonhyperfiniteness.

Notes
2021 Jun 25 Speaker: Anush Tserunyan (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 5: the 99% lemma and
the Kaimanovich–Elek theorem
Abstract

We begin by presenting µ-hyperfiniteness of locally finite graphs as almost finiteness (the 99% lemma) and use this to prove a characterization of µ-hyperfiniteness in terms of the isoperimetric constant (the Kaimanovich–Elek theorem).

Notes
2021 Jun 18 Speaker: Anush Tserunyan (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 4: combining the hyperfinite and superquadratic
growth cases
Abstract

Assuming a characterization of µ-hyperfiniteness in terms of the isoperimetric constant (Kaimanovich–Elek theorem), we explain how nowhere µ-hyperfiniteness implies the existence of a Borel a.e. one-ended spanning subforest.

Notes
2021 Jun 11 Speaker: Jenna Zomback (University of Illinois Urbana-Champaign)
Title: On one-ended spanning subforests and treeability of groups, part 3: one-ended subforests in pmp graphs of
superquadratic growth
Abstract

In the third talk on this paper, we continue to investigate which graphs have a.e. spanning subforests. We prove that any pmp graph of superquadratic growth has an a.e. spanning subforest by demonstrating a sufficient condition for having such a subforest.

Notes
2021 Jun 4 Speaker: Matthew Bowen (McGill University)
Title: On one-ended spanning subforests and treeability of groups, part 2: one-ended subforests in hyperfinite graphs
Abstract

We give a brief introduction to the use of one-ended spanning trees and forests in descriptive graph combinatorics and characterize which hyperfinite locally finite Borel graphs admit a.e. one-ended spanning subforests.

Annotated slides
2021 May 28 Speaker: Ruiyuan (Ronnie) Chen (University of Illinois Urbana-Champaign)
Title: On one-ended spanning subforests and treeability of groups, part 1: introduction
Annotated slides
2021 May 20 Speaker: Nishant Chandgotia (TIFR Bangalore)
Title: About Borel and almost Borel embeddings for d actions
Abstract

Krieger's generator theorem says that all free ergodic measure preserving ℤ actions (under natural entropy constraints) can be modelled by a full shift. Following results by Anush Tserunyan and answering a question by Benjamin Weiss, in a sequence of two papers Mike Hochman noticed that this theorem can be strengthened: He showed that all free homeomorphisms of a Polish space (under entropy constraints) can be Borel embedded into the full shift. In this talk we will discuss some results along this line from a recent paper with Tom Meyerovitch and ongoing work with Spencer Unger.

Slides
2021 Apr 28 Speaker: Sohail Farhangi (Ohio State University)
Title: Connections between van der Corput's Difference Theorem and the Ergodic Hierarchy of Mixing
Abstract

We will begin with an overview of the classical van der Corput Difference Theorem and some of its Hilbertian variants that are useful in Ergodic Theory, including the variant that is used in the proof of Szemeredi's Theorem. We will then briefly review the ergodic hierarchy of mixing and point out the similarities to the existing variants of van der Corput's Theorem. Afterwards, we will state generalizations of the existing variants of van der Corput's Difference Theorem in Hilbert spaces that demonstrate connections to weak mixing, mild mixing, strong mixing, and Bernoulli (this last connection is more delicate than the rest). We will also be able to state a new Hilbertian variant of van der Corput's Difference Theorem corresponding to ergodicity. If time permits, we will state mixing van der Corput Difference Theorems in the context of uniform distribution.

Slides
2021 Apr 21 Speaker: Antoine Poulin (McGill University)
Title: On metrizability of universal minimal flows of homeomorphism groups of manifolds, part 2
Abstract

In these two talks, we will discuss a result by Gutman, Tsankov, and Zucker, where non-metrizability of the universal minimal flow of the homeomorphism groups of high dimensional manifolds is established. The proof uses ingenious technology in the form of the space of maximal connected chains, as well as geometric property inherited from the charts.

Notes
2021 Apr 14 Speaker: Antoine Poulin (McGill University)
Title: On metrizability of universal minimal flows of homeomorphism groups of manifolds, part 1
Abstract

In these two talks, we will discuss a result by Gutman, Tsankov, and Zucker, where non-metrizability of the universal minimal flow of the homeomorphism groups of high dimensional manifolds is established. The proof uses ingenious technology in the form of the space of maximal connected chains, as well as geometric property inherited from the charts.

Notes
2021 Apr 7 Joint with McGill Geometric Group Theory Seminar
Speaker: Joshua Frisch (Caltech)
Title: The ICC property in Random Walks and Dynamics
Abstract

A topological dynamical system (i..e a group acting by homeomorphisms on a compact Hausdorff space) is said to be proximal if for any two points p and q we can simultaneously "push them together" (rigorously, there is a net gn such that limgn(p) = limgn(q)). In his paper introducing the concept of proximality, Glasner noted that whenever ℤ acts proximally, that action will have a fixed point. He termed groups with this fixed point property “strongly amenable”.
  The Poisson Boundary of a random walk on a group is a measure space that corresponds to the space of different asymptotic trajectories that the random walk might take. Given a group G and a probability measure μ on G the Poisson boundary is trivial (i.e. has no non-trivial events) if and only if G supports a bounded mu-harmonic function. A group is Called Choquet Deny if its Poisson Boundary is trivial for every μ.
  In this talk I will discuss work giving an explicit classification of which groups are Choquet Deny, which groups are strongly amenable, and what these mysteriously equivalent classes of groups have to do with the ICC property. I will also discuss why strongly amenable groups can be viewed as strengthening amenability in at least three distinct ways thus proving the name is extremely well deserved.
  This is joint work with Yair Hartman, Omer Tamuz, and Pooya Vahidi Ferdowsi.

2021 Mar 31 Speaker: Sławomir Solecki (Cornell University)
Title: Random continuum and iterated Brownian motion
Abstract

We describe a probabilistic model involving iterated Brownian motion for constructing a random chainable continuum. We show that this random continuum is indecomposable. We use our probabilistic model to define a Wiener-type measure on the space of all chainable continua. This is joint work with Viktor Kiss.

Slides
2021 Mar 24 Speaker: Anton Bernshteyn (Georgia Tech)
Title: Probabilistic tools in continuous combinatorics
Abstract

In this talk I will describe probabilistic tools that can be used to construct continuous solutions to combinatorial problems on zero-dimensional spaces. I will also discuss some applications of these tools. In particular, I will outline an equivalence between certain problems in two seemingly disparate subjects: continuous combinatorics and distributed computing.

Slides
2021 Mar 17 Speaker: Prakash Panangaden (McGill University)
Title: The Logical Characterization of Probabilistic Bisimulation
Abstract

Probabilistic bisimulation is an equivalence relation on the states of a Labelled Markov Process that captures behavioural equivalence. It was introduced by Larsen and Skou in the late 1980s following the definition of bisimulation for nondeterministic transition systems in the 1970s by Park and Milner. I and my coworkers extended the theory to systems with continuous state spaces. In particular we showed that one can characterize bisimulation by a modal logic, which, surprisingly, was much simpler than the logic previously used to characterize probabilistic bisimulation on discrete state spaces. We were able to do this by using ideas from descriptive set theory specifically the concept of smooth equivalence relation and the unique structure theorem for analytic spaces. Later we extended these results to cover simulation as well. Still later this work was extended to MDPs and to metric analogues of bisimulation. I will give an expository talk assuming the audience knows all the relevant measure theory and descriptive set theory but not the computer science concepts like bisimulation. I will use a tablet to give a “chalkboard” talk rather than slides. This is joint work with Josée Desharnais, Abbas Edalat and then later with Josée Desharnais, Radha Jagadeesan and Vineet Gupta and finally with Florence Clerc, Nathanael Fijalkow and Bartek Klin.

2021 Mar 10 Speaker: Shrey Sanadhya (University of Iowa)
Title: Generalized Bratteli Vershik model for substitution on infinite alphabets
Abstract

We consider substitutions on countably infinite alphabets as Borel dynamical system and build their Bratteli-Vershik models. We prove two versions of Rokhlin’s lemma for such substitution dynamical systems. Using the Bratteli-Vershik model we give an explicit formula for a shift-invariant measure (finite and infinite) and provide a criterion for this measure to be ergodic. This is joint work with Sergii Bezuglyi and Palle Jorgensen.

Annotated slides
2021 Mar 3 Speaker: Matthiew Bowen (McGill University)
Title: Descriptive graph combinatorics and the Kechris-Solecki-Todorcevic dichotomy, part 2
Abstract

In this series of two talks, we will give a brief introduction to the field of descriptive graph combinatorics and present a new proof of the Kechris-Solecki-Todorcevic (KST) dichotomy discovered independently by Anton Bernshteyn and Ben Miller. During the first talk we will discuss some key examples and results from this field, including the KST dichotomy and its applications. In the second talk we will go over Anton and Ben's proof in detail.

2021 Feb 24 Speaker: Matthiew Bowen (McGill University)
Title: Descriptive graph combinatorics and the Kechris-Solecki-Todorcevic dichotomy, part 1
Abstract

In this series of two talks, we will give a brief introduction to the field of descriptive graph combinatorics and present a new proof of the Kechris-Solecki-Todorcevic (KST) dichotomy discovered independently by Anton Bernshteyn and Ben Miller. During the first talk we will discuss some key examples and results from this field, including the KST dichotomy and its applications. In the second talk we will go over Anton and Ben's proof in detail.

2021 Feb 17 Speaker: Michael Wolman (Caltech)
Title: Probabilistic Programming Semantics for Name Generation, part 3: the proof
Abstract

In this series of talks we present a probabilistic model for name generation. Specifically, we interpret the nu-calculus, a simply-typed lambda-calculus with name generation, in the category of quasi-Borel spaces, an extension of the category of standard Borel spaces supporting both measure theory and higher-order programming. We prove that this model is fully abstract at first-order types. This is joint work with Marcin Sabok, Sam Staton and Dario Stein.
  In part 3 of this series, we present the proof of full abstraction of the nu-calculus in the category of quasi-Borel spaces. It will be a nice mix of programming language theory and descriptive set theory. On the programming language side, we will use logical relations to construct a normal form for the nu-calculus eliminating private names. On the descriptive set theory side, we will use a pmp action and a pair of Borel-inseparable sets to prove that passing to the normal form is valid in QBS.

2021 Feb 3 Speaker: Michael Wolman (Caltech)
Title: Probabilistic Programming Semantics for Name Generation, part 2
Abstract

In this series of talks we present a probabilistic model for name generation. Specifically, we interpret the nu-calculus, a simply-typed lambda-calculus with name generation, in the category of quasi-Borel spaces, an extension of the category of standard Borel spaces supporting both measure theory and higher-order programming. We prove that this model is fully abstract at first-order types. This is joint work with Marcin Sabok, Sam Staton and Dario Stein.

2021 Jan 26 Speaker: Michael Wolman (Caltech)
Title: Probabilistic Programming Semantics for Name Generation, part 1
Abstract

In this series of talks we present a probabilistic model for name generation. Specifically, we interpret the nu-calculus, a simply-typed lambda-calculus with name generation, in the category of quasi-Borel spaces, an extension of the category of standard Borel spaces supporting both measure theory and higher-order programming. We prove that this model is fully abstract at first-order types. This is joint work with Marcin Sabok, Sam Staton and Dario Stein.