Lie-Størmer Colloquium

Program

Complexity of computing complex zeros of structured polynomial systems                                             

What does universal mean? What is its scope? And how does it relate to undecidability?

Tantalizing patterns of closed curves on surfaces which became theorems

Dynamic programming and Hopf algebras                                                                                                  

Orthogonal systems that recover invariants on the real line                                             

Algorithms on very large graphs

Good locally testable codes

An open conjecture on colliding permutations

Post-Lie algebras and affine connections                                  

Deep learning from the perspective of optimal control, stable numerical methods for ODEs and group equivariance

Forest formulas and the  Magnus operator                                                                                                                                       

The Value of Errors in Proofs (a fascinating journey from Turing's 1936 seminal R ≠ RE to the 2020 breakthrough of MIP* = RE)

Gathering chestnuts of math related to fluid motion

An introduction to graph limits       

Peter Bürgisser
Complexity of computing complex zeros of structured polynomial systems

Can we solve polynomial systems in polynomial time? This question received different answers in different contexts. The NP-hardness of deciding the feasibility of a general polynomial system does not preclude efficient algorithms for computing complex zeros of polynomial systems with as many equations as variables, on which the feasibility is granted under genericity hypotheses.  
 
Smale’s 17th problem is a clear-cut formulation of the problem in a numerical setting. We report on recent progress that gives a positive answer to a refinement of Smale’s question for structured systems. 
 
Joint work with Felipe Cucker and Pierre Lairez: 
Powered by
Gemma de las Curvas
What does universal mean? What is its scope? And how does it relate to undecidability?

Universal means “all-encompassing”. Many forms of universality are known: Some have a formal definition (universal Turing machines, universal spin models, universal neural networks, universal graphs,…), while others do not (universal grammar, the problem of universals in philosophy,…). Here we express them all as instances of a basic idea of universality, and, whenever possible, we formalise this idea, devise several types of universality, and compare characterisations. This allows us to explore the reach of universality across disciplines.

Powered by
Moira Chas
Tantalizing patterns of closed curves on surfaces which became theorems

Consider an orientable surface S with negative Euler characteristic, a minimal set of generators of the fundamental group of S, and a nice  hyperbolic metric on S. Each deformation class C of closed directed curves on S determines three numbers: the word length (that is, the minimal number of letters needed to express C as a cyclic word in the generators and their inverses), the minimal geometric self-intersection number, and the geometric length.  Finally, there is a Goldman Lie bracket on the linear combinations of such curves  defined by the minimal  intersection structure of curves on S.
We will discuss  algorithms to obtain  these  numbers and structure, and how computer experiments using these algorithms led to counterexamples to existing conjectures, formulations of new conjectures and (sometimes) subsequent theorems.
(These results are joint work with different collaborators; mainly Arpan Kabiraj, Steven Lalley and Rachel Zhang)
Powered by
Joscha Diehl
TBA

Powered by
Arieh Iserles
Orthogonal systems that recover invariants on the real line

Many invariants of time-evolving PDEs, e.g. mass and some Hamiltonians, can be formulated as a bilinear form. In this talk we are concerned with formal orthogonal systems on the real line (and, by tensorisation, in $\mathbb{R}^d$) with respect to bilinear forms and with a tridiagonal differentiation matrix. The theory is virtually complete for $L_2$ and Sobolev inner products: using a Fourier transform we show that such systems are in a one-to-one relationship with determinate Borel measures and that their closure is a Paley–Wiener space. We provide several examples, commencing from the familiar Hermite functions. We also characterise all such systems that can be computed fast – for $L_2$ orthogonality using Fast Fourier/Cosine/Sine Transform, for Sobolev orthogonality the above in tandem with a narrow-banded matrix of connection coefficients. We conclude with preliminary results on systems that are orthogonal with respect to a bilinear form generated by the Hamiltonian of a linear Schrödinger equation. This is joint work with Marcus Webb.
Powered by
László Lovász
Algorithms on very large graphs

An algorithmic theory of very large graphs (think of billions of nodes, like the internet or the contact network of people) represents new challenges. The graph itself is not completely known, changes all the time, and the data set is too large to handle. Some types of questions make no sense at all, for others only an approximate answer can be given. Often the desired answer (like a maximum cut) is in itself to large to be returned. In this talk we sketch approaches to these questions, some classical by now, some newer. The P versus NP question has an analogue in this setting, and it has the somewhat surprising answer that P=NP for this model.
Powered by
Alex Lubotzky
Good locally testable codes

An error-correcting code is locally testable (LTC) if there is a random tester that reads only a small number of bits of a given word and decides whether the word is in the code, or at least close to it.

A long-standing problem asks if there exists such a code that also satisfies the golden standards of coding theory: constant rate and constant distance Unlike the classical situation in coding theory, random codes are not LTC, so this problem is a challenge of a new kind. We construct such codes based on what we call (Ramanujan) Left/Right Cayley square complexes. These are 2-dimensional versions of the expander codes constructed by Sipser and Spielman (1996). The main result and lecture will be self-contained. But we hope also to explain how the seminal work Garland ( 1972) on the cohomology of quotients of the Bruhat-Tits buildings of p-adic Lie group has led to this construction ( even though it is not used at the end)

 Based on joint work with I. Dinur, S. Evra, R. Livne, and S. Mozes.

Powered by
Claudia Malvenuto
An open conjecture on colliding permutations

In the talk, I would like to illustrate some results and an open conjecture in the area of extremal combinatorics of permutations.
We call two permutations of the first $n$ naturals colliding if they map at least one number to consecutive naturals. The notion has been introduced in 2006 by János Korner and myself. We asked for the maximum number of pairwise colliding permutations of $n$. We conjectured that such a maximum is assumed in the nth-central binomial coefficient. The notion of colliding permutations has an information theoretic flavour, since it can be described as “permutation capacity” of infinite graphs.

Variations such as cyclic colliding permutations (with Gerard Cohen), or graph-different permutations (with J. Korner and Gábor Simonyi) have been considered later. I will give an account of the `state of the art’ on this still open conjecture, to exchange and discuss ideas during the Colloquium.

Powered by
Dominique Manchon
Post-Lie algebras and affine connections

Following the pioneering work by A. Cayley on vector  elds and rooted trees in 1857, it has been well-known for several decades that the Lie algebra of vector  fields on an a ne space is a pre-Lie algebra, due to the presence of a flat torsion-free affine connection. More recently, vector  fields on a homogeneous space appeared to form a post-Lie algebra, due to the presence of a natural flat connection with constant torsion. The notion of post-Lie algebra appeared, together with the name, for the first time in 2007 the work of B. Vallette. I will explain in this talk how post-Lie algebras also appear in the study of vector  fields on any smooth manifold endowed with an a affine connection, possibly with non-vanishing curvature and torsion.
Based on joint work with Mahdi J. H. Al-Kaabi, Kurusch Ebrahimi-Fard and Hans Z. Munthe-Kaas.

Powered by
Brynjulf Owren
Deep learning from the perspective of optimal control, stable numerical methods for ODEs and group equivariance

Supervised deep learning can be thought of as a way of approximating an unknown function based on a set of data samples. The space of approximating functions is represented by a neural network. The residual neural networks constitute a particular type of network architecture that enjoys a close connection to ordinary differential equations, the so called neural ODE. The training of the network can in this sense be cast as a continuous optimal control problem. This allows for a number of opportunities for discretizations and analysis of the resulting dynamical system. In order to reduce the sensitivity to adversarial attacks, one may argue that the input-tooutput map of the neural networks should be 1-Lipschitz. We discuss here, by using some well established theory for contractivity of numerical methods, how this can be achieved. Another important issue is that of equivariance of the neural networks with respect to some natural group actions. The purpose of this is to reduce the required amount of data in the model and to avoid data augmentation. Finally, we shall give some examples of the use of these ideas to inverse problems and for learning mechanical systems.

Powered by
Frédéric Patras
Forest formulas and the Magnus operator

The forest formulas that have appeared in perturbative quantum field theory are
optimal in a certain sense (they have a minimal number of terms and avoid overcounting).
They were later understood as having a general validity in the context of
preLie calculus. In this talk, we extend their validity to the context of the Baker-
Campbell-Hausdorff problem. As an example of application, we will apply the general method to recover results by Murua related to the Magnus operator.

Joint work with A. Celestino.

Avi Wigderson
The Value of Errors in Proofs (a fascinating journey from Turing's 1936 seminal R ≠ RE to the 2020 breakthrough of MIP* = RE)

Last year, a group of theoretical computer scientists posted a paper on the Arxiv with the strange-looking title “MIP* = RE”, impacting and surprising not only complexity theory but also some areas of math and physics. Specifically, it resolved, in the negative, the “Connes’ embedding conjecture” in the area of von-Neumann algebras, and the “Tsirelson problem” in quantum information theory. You can find the paper herehttps://arxiv.org/abs/2001.04383. As it happens, both acronyms MIP* and RE represent proof systems, of a very different nature. To explain them, we’ll take a meandering journey through the classical and modern definitions of proof. I hope to explain how the methodology of computational complexity theory, especially modeling and classification (both problems and proofs) by algorithmic efficiency, naturally leads to the generation of new such notions and results (and more acronyms, like NP). A special focus will be on notions of proof which allow interaction, randomness, and errors, and their surprising power and magical properties.

The talk does not assume any special mathematical background.

 

Powered by
Dennis Sullivan
Gathering chestnuts of math related to fluid motion

By now the beautiful equations modeling incompressible fluid motion in three dimensional space have been singled out by a precise yes or no mathematical question that appears among the Clay Millennium Problems. If the answer is yes this gives credence to continue using only this model to build algorithms that will better predict and compute the complicated motion of fluids. If the answer is no the motivation for using this model for said algorithms persists especially if the counterexamples are not generic.
However, the existence of observed turbulence with lots of structure suggests new ideas perturbing current modeling are called for. The lecture is about a few modest insights into this issue that have accrued over three decades of personal curiosity. These ideas can be used to make new algorithms.

Powered by
Katalin Vesztergombi
An introduction to graph limits

The theory of graph limits is most developed in the case of dense graphs. There is well understood notion of convergence and of the limit objects. The goal of this talk is to give a gentle introduction to this theory, giving some interesting examples, and describing the basic theorems.

Powered by