ETH Zurich

In this talk, I will present new results addressing two rather well-known problems on the embeddability of planar graphs on point-sets in the plane. The first problem, often attributed to Mohar, asks for the asymptotics of the minimum size of so-called universal point sets, i.e. point sets that simultaneously allow straight-line embeddings of all planar graphs on $n$ vertices. In the first half of the talk I will present a family of point sets of size $O(n)$ that allow straight-line embeddings of a large family of $n$-vertex planar graphs, including all bipartite planar graphs. In the second half of the talk, I will present a family of $(3+o(1))\log_2(n)$ planar graphs on $n$ vertices that cannot be simultaneously embedded straight-line on a common set of $n$ points in the plane. This significantly strengthens the previously best known exponential bound.

I will discuss a line of work on estimating causal effects from observational data. In the first part of the talk, I will discuss identification and estimation of causal effects when the underlying causal graph is known, using adjustment. In the second part, I will discuss what one can do when the causal graph is unknown. Throughout, examples will be used to illustrate the concepts and no background in causality is assumed.

Generative AI has seen tremendous successes recently, most notably the chatbot ChatGPT and the DALLE2 software creating realistic images and artwork from text descriptions. Underlying these and other generative AI systems are usually neural networks trained to produce text, images, audio, or video from text inputs. The aim of this talk is to develop an understanding of the fundamental capabilities of generative neural networks. Specifically and mathematically speaking, we consider the realization of high-dimensional random vectors from one-dimensional random variables through deep neural networks. The resulting random vectors follow prescribed conditional probability distributions, where the conditioning represents the text input of the generative system and its output can be text, images, audio, or video. It is shown that every d-dimensional probability distribution can be generated through deep ReLU networks out of a 1-dimensional uniform input distribution. What is more, this is possible without incurring a cost—in terms of approximation error as measured in Wasserstein-distance—relative to generating the d-dimensional target distribution from d independent random variables. This is enabled by a space-filling approach which realizes a Wasserstein-optimal transport map and elicits the importance of network depth in driving the Wasserstein distance between the target distribution and its neural network approximation to zero. Finally, we show that the number of bits needed to encode the corresponding generative networks equals the fundamental limit for encoding probability distributions (by any method) as dictated by quantization theory according to Graf and Luschgy. This result also characterizes the minimum amount of information that needs to be extracted from training data so as to be able to generate a desired output at a prescribed accuracy and establishes that generative ReLU networks can attain this minimum.

This is joint work with D. Perekrestenko and L. Eberhard


 

Over the last years, two different approaches to construct symmetry algebras acting on the cohomology of Nakajima quiver varieties have been developed. The first one, due to Maulik and Okounkov, exploits certain Lagrangian correspondences, called stable envelopes, to generate R-matrices for an arbitrary quiver and hence, via the RTT formalism, an algebra called Yangian. The second one realises the cohomology of Nakajima varieties as modules over the cohomological Hall algebra (CoHA) of the preprojective algebra of the quiver Q. It is widely expected that these two approaches are equivalent, and in particular that the Maulik-Okounkov Yangian coincides with the Drinfel’d double of the CoHA.

Motivated by this conjecture, in this talk I will show how to identify the stable envelopes themselves with the multiplication map of a subalgebra of the appropriate CoHA. 

As an application, I will introduce explicit inductive formulas for the stable envelopes and use them to produce integral solutions of the elliptic quantum Knizhnik–Zamolodchikov–Bernard (qKZB) difference equation associated to arbitrary quiver (ongoing project with G. Felder and K. Wang). Time permitting, I will also discuss connections with Cherkis bow varieties in relation to 3d Mirror symmetry (ongoing project with R. Rimanyi).

In this talk we discuss solution of the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an $n$-vertex graph can have without containing a $k$-regular subgraph, for some fixed integer $k\geq 3$. We prove that any $n$-vertex graph with average degree at least $C_k\log\log n$ contains a $k$-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially
improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough.

Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree.

Joint work with Oliver Janzer

The size-Ramsey number $\hat{r}(H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have, such that for any red/blue coloring of $G$, there is a monochromatic copy of $H$ in $G$. Recently, Conlon, Nenadov and Trujić showed that if $H$ is a graph on $n$ vertices and maximum degree three, then $\hat{r}(H) = O(n^{8/5})$, improving upon the bound of $n^{5/3 + o(1)}$ by Kohayakawa, Rödl, Schacht and Szemerédi. In our paper, we show that $\hat{r}(H)\leq n^{3/2+o(1)}$. While the previously used host graphs were vanilla binomial random graphs, we prove our result by using a novel host graph construction.
We also discuss why our bound is a natural barrier for the existing methods.
This is joint work with Kalina Petrova.

Combining physics with machine learning is a rapidly growing field of research. Thereby, most work focuses on leveraging machine learning methods to solve problems in physics. Here, however, we focus on the reverse direction of leveraging structure of physical systems (e.g. dynamical systems modeled by ODEs or PDEs) to construct novel machine learning algorithms, where the existence of highly desirable properties of the underlying method can be rigorously proved. In particular, we propose several physics-inspired deep learning architectures for sequence modelling as well as for graph representation learning. The proposed architectures mitigate central problems in each corresponding domain, such as the vanishing and exploding gradients problem for recurrent neural networks or the oversmoothing problem for graph neural networks. Finally, we show that this leads to state-of-the-art performance on several widely used benchmark problems.

Wasserstein distance induces a natural Riemannian structure for the probabilities on the Euclidean space. This insight of classical transport theory is fundamental for tremendous applications in various fields of pure and applied mathematics. We believe that an appropriate probabilistic variant, the adapted Wasserstein distance $AW$, can play a similar role for the class $FP$ of filtered processes, i.e. stochastic processes together with a filtration. In contrast to other topologies for stochastic processes, probabilistic operations such as the Doob-decomposition, optimal stopping and stochastic control are continuous w.r.t. $AW$. We also show that $(FP, AW)$ is a geodesic space, isometric to a classical Wasserstein space, and that martingales form a closed geodesically convex subspace. Finally we consider computational aspects and provide a novel method based on the Sinkhorn algorithm.

The talk is based on articles with Daniel Bartl, Mathias Beiglböck and Stephan Eckstein.

A proposal for the worldsheet string theory that is dual to free N=4 SYM in 4d will be explained. It is described by a free field sigma model on the twistor space of AdS5 x S5, and is a direct generalisation of the corresponding model for tensionless string theory on AdS3 x S3. I will explain how our proposal fits into the general framework of AdS/CFT, and review the various checks that have been performed.