L4

We show the super-hedging duality for multi-action options which generalise American options to a larger space of actions (possibly uncountable) than {stop, continue}. We put ourselves in the framework of Bouchard & Nutz model relying on analytic measurable selection theorem. Finally we consider information delay on the action component of the product space. Information delay is expressed as a possibility to look into the future in the dual formulation. This is a joint work with Ivan Guo, Shidan Liu and Zhou Zhou.

We consider the reinforcement learning problem of controlling an unknown dynamical system to maximise the long-term average reward along a single trajectory. Most of the literature considers system interactions that occur in discrete time and discrete state-action spaces. Although this standpoint is suitable for games, it is often inadequate for systems in which interactions occur at a high frequency, if not in continuous time, or those whose state spaces are large if not inherently continuous. Perhaps the only exception is the linear quadratic framework for which results exist both in discrete and continuous time. However, its ability to handle continuous states comes with the drawback of a rigid dynamic and reward structure.

        This work aims to overcome these shortcomings by modelling interaction times with a Poisson clock of frequency $\varepsilon^{-1}$ which captures arbitrary time scales from discrete ($\varepsilon=1$) to continuous time ($\varepsilon\downarrow0$). In addition, we consider a generic reward function and model the state dynamics according to a jump process with an arbitrary transition kernel on $\mathbb{R}^d$. We show that the celebrated optimism protocol applies when the sub-tasks (learning and planning) can be performed effectively. We tackle learning by extending the eluder dimension framework and propose an approximate planning method based on a diffusive limit ($\varepsilon\downarrow0$) approximation of the jump process.

        Overall, our algorithm enjoys a regret of order $\tilde{\mathcal{O}}(\sqrt{T})$ or $\tilde{\mathcal{O}}(\varepsilon^{1/2} T+\sqrt{T})$ with the approximate planning. As the frequency of interactions blows up, the approximation error $\varepsilon^{1/2} T$ vanishes, showing that $\tilde{\mathcal{O}}(\sqrt{T})$ is attainable in near-continuous time.

In this short course, we survey the celebrated weak and strong compactness theorems proved by Karen Uhlenbeck in 1982. These results are fundamental to the gauge theory and have found numerous applications to geometry, topology, and theoretical physics. The proof is based on the ingenious idea of putting connections into ``Uhlenbeck--Coulomb gauge'', which enables the use of standard elliptic and/or nonlinear PDE techniques, as well as involved local-to-global patching arguments. We aim at giving detailed explanation of the proof, and we shall also discuss the relation between Uhlenbeck's compactness and the classical geometric problem of isometric immersions of submanifolds into Euclidean spaces.

An $n$-vertex graph $G$ is a $C$-expander if $|N(X)|\geq C|X|$ for every $X\subseteq V(G)$ with $|X|< n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices.

We show that there is some constant $C>0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda)$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications.

Joint work with R. Montgomery, D. Munhá Correia, A. Pokrovskiy and B. Sudakov.

The handlebody group is defined to be the mapping class group of a handelbody (rel. boundary). It is a subgroup of the mapping class group of the surface of the handlebody, and maps onto the outer automorphism group of its fundamental group (the free group of rank equal to its genus). 

Recently Hainaut and Petersen described a subspace of moduli space forming an orbifold classifying space for the handlebody group, and combined this with work of Chan-Galatius-Payne to construct cohomology classes in the group. I will talk about how one can build on their ideas to define a cocompact EG for the handlebody group inside Teichmüller space. This is a manifold with boundary and comes with a filtration by labelled disk systems which we call the `RGB (red-green-blue) disk complex.' I will describe this filtration, use it to describe the boundary of the manifold, and speculate about potential applications to duality results. Based on work-in-progress with Dan Petersen.

Brown-Erdős-Sós initiated the study of the maximum number of edges in an $n$-vertex $r$-graph such that no $k$ edges span at most $s$ vertices. If $s=rk-2k+2$ then this function is quadratic in $n$ and its asymptotic was previously known for $k=2,3,4$. I will present joint work with Stefan Glock, Jaehoon Kim, Lyuben Lichev and Shumin Sun where we resolve the cases $k=5,6,7$.

What is the bare minimum needed to get a unitarity-consistent black hole radiation entropy curve? In this talk, I will show how to capture both Hawking's non-unitary entropy curve, and density matrix-connecting contributions that restore unitarity, in a toy quantum system with chaotic dynamics. The motivation is to find the simplest possible dynamical model, dropping all superfluous details, that captures this aspect of gravitational physics. In the model, the Hamiltonian obeys random matrix statistics within microcanonical windows, the entropy of the averaged state gives the non-unitary curve, the averaged entropy gives the unitary curve, and the difference comes from matrix index contractions in the Haar averaging that connect the density matrices in a replica wormhole-like manner.

Given a matrix $A$ with integer entries, a subset $S$ of an abelian group and $r\in\mathbb N$, we say that $S$ is $(A,r)$-Rado if any $r$-colouring of $S$ yields a monochromatic solution to the system of equations $Ax=0$. A classical result of Rado characterises all those matrices $A$ such that $\mathbb N$ is $(A,r)$-Rado for all $r \in \mathbb N$. Rödl and Ruciński, and Friedgut, Rödl and Schacht proved a random version of Rado’s theorem where one considers a random subset of $[n]:=\{1,\dots,n\}$.

In this paper, we investigate the analogous random Ramsey problem in the more general setting of abelian groups. Given a sequence $(S_n)_{n\in\mathbb N}$ of finite subsets of abelian groups, let $S_{n,p}$ be a random subset of $S_n$ obtained by including each element of $S_n$ independently with probability $p$. We are interested in determining the probability threshold for $S_{n,p}$ being $(A,r)$-Rado.

Our main result is a general black box for hypergraphs which we use to tackle problems of this type. Using this tool in conjunction with a series of supersaturation results, we determine the probability threshold for a number of different cases. A consequence of the Green-Tao theorem is the van der Waerden theorem for the primes: every finite colouring of the primes contains arbitrarily long monochromatic arithmetic progressions. Using our machinery, we obtain a random version of this result. We also prove a novel supersaturation result for $[n]^d$ and use it to prove an integer lattice generalisation of the random version of Rado's theorem.

This is joint work with Andrea Freschi and Andrew Treglown (both University of Birmingham).

I will then explain that hybrid quantum-classical protocols are the most promising candidates for achieving early quantum advantage. These have the potential to solve real-world problems---including optimisation or ground-state search---but they suffer from a large number of circuit repetitions required to extract information from the quantum state. I will explain some of our recent results as hybrid quantum algorithms that exploit so-called classical shadows (random unitary protocols) in order to extract and post-process a large amount of information from the quantum computer [PRX 12, 041022 (2022)] and [arXiv:2212.11036]. I will finally identify the most likely areas where quantum computers may deliver a true advantage in the near term.