KdVI General Mathematics Colloquium

Structure-versus-randomness in combinatorics and complexity

What does it mean for an object to look random? How can its level of randomness be measured? Seminal work of Chung, Graham and Wilson gave satisfactory answers when the objects are dense graphs, in which case the number of four-cycles can serve as a measure.

In this talk I will discuss another answer to these questions in a setting related to a famous 1975 result of Szemerédi, which says that any dense subset of the positive integers must contain arbitrarily long arithmetic progressions. In a spectacular new proof of Szemerédi's theorem, Gowers introduced a measure of randomness for functions on finite abelian groups in the form of norms, now called the Gowers uniformity norms. These norms have the extremely useful property that a truly random function will typically have a tiny uniformity norm, while any (bounded) function with a large uniformity norm must necessarily have a lot of "structure".

I will also discuss the relevance of this structure to refinements of Szemerédi's theorem that resulted from a famous ergodic-theoretic proof of Furstenburg, and how similar ideas appear in the study of quantum-versus-classical computational complexity.

Algebraic structures in topology

One of the main goals of topology is to determine whether two topological spaces can be continuously deformed into each other. The main method for doing this is by turning spaces into algebraic objects, like groups, rings, etc, which are much easier to manipulate. In this talk I give an overview of how this is done and explain that when we make these algebraic objects complicated enough topological problems can be translated into completely algebraic problems.

Randomness - the Utility of Unpredictability

Is the universe inherently deterministic or probabilistic? Perhaps more importantly - can we tell the difference between the two? Humanity has pondered the meaning and utility of randomness for millennia. There is a remarkable variety of ways in which we utilize perfect coin tosses to our advantage: in statistics, cryptography, game theory, algorithms, gambling... Indeed, randomness seems indispensable!

Which of these applications survive if the universe had no randomness in it at all? Which of them survive if only poor-quality randomness is available, e.g. that arises from "unpredictable" phenomena like the weather or the stock market? A computational theory of randomness, developed in the past three decades, reveals (perhaps counter-​intuitively) that very little is lost in such deterministic or weakly random worlds. In the talk I'll explain the main ideas and results of this theory.

No special background will be assumed.

Rational points on Fano varieties

Fano varieties form one of the fundamental classes of building blocks in the birational classification of algebraic varieties. In this talk I will discuss how their special geometric properties can be used to study their arithmetic. I will focus on a few conjectures about their rational points over number fields (potential density, Manin's conjecture) and how they can be investigated by determining the asymptotic behavior of certain counting functions of rational points. All the main objects involved will be introduced and illustrated by examples. A summary of the literature on the topic will be discussed, including my own contribution.

How GNNs and Symmetries can help to solve PDEs

Deep learning has seen amazing advances over the past years, completely replacing traditional methods in fields such as speech recognition, natural language processing, image and video analysis and so on. A particularly versatile deep architecture that has gained much traction lately is the graph neural network (GNN), of which transformers represent a special case. GNNs have the desirable property that they can process graph structured data while respecting permutation symmetry. Recently, GNNs have found new applications in scientific computation, for instance to predict the properties of molecules or to predict the forces that act on atoms when they evolve (e.g. fold). In this application it is also key that geometric symmetries, such as translation and rotation symmetries are taken into consideration. Professor Max Welling will report on yet another exciting application of using GNNs to solve partial differential equations (PDEs). It turns out that GNNs are an excellent tool to develop neural PDE integrators. Moreover, PDEs are full of surprising symmetries that can be leveraged to train neural integrators with less data. Professor Max Welling will discuss this very exciting new chapter in deep learning. He will end with a discussion of whether reversely, PDEs can also serve as a model for new deep architectures.

Joint work with Johannes Brandstetter and Daniel Worrall.

The relevance of the Mandelbrot set in combinatorics, statistical physics, and computational complexity theory

I will make a case for the relevance of the Mandelbrot set in the seemingly unrelated area of mathematics hinted at in the title. The case is partially based on joint works with Ferenc Bencs, David de Boer, Pjotr Buys, Lorenzo Guerini and Guus Regts.

Moduli spaces: "counting" in and outside algebraic geometry

Suppose one wants to classify all objects with certain properties. A geometric space whose points correspond one-to-one with these objects is called a moduli space. The study of moduli spaces is classical and important: not only do they give insight in the classified objects and the relation between these objects, but they also often have very interesting geometric properties themselves. In this talk I will explain more precisely what moduli spaces are, give many examples, and explain how they come up in my work.

A randomized k-centrality measure & applications to networks node immunization

Have you ever thought how you can “immunize" a network from an attack of a viral agent? This is a hot topic in network science and it consists in identifying and removing a set of nodes of a given size in a graph to maximally impede the virus spread. Based on the stability analysis of so-called compartmental models (classical simple models for contagion which will be briefly recalled and discussed), the maximal eigenvalue of the adjacency matrix of the graph has been proposed as a measure for how much resilient the network is. Thus, one of the most common approaches for immunization consists in identifying the set of nodes of a given cardinality, for which the reduced network (obtained by removing these nodes and their incident edges) has smallest maximal eigenvalue. The question is, how can we efficiently identify such a set of nodes? We present a new flexible algorithm based on random walks which may also have applications in other network optimization problems.

Joint work with Michael Emmerich, Alex Gaudilliere and Irina Gurewitsch.