The videos are also published and available online.
- László Lovász (Eötvös Loránd University, Budapest)
Graph limits meet Markov chains (presentation)
Abstract:
To define the limit of a sequence of graphs which are neither dense nor very sparse is perhaps the most important question in graph limit theory. Several convergence notions have been proposed (Frenkl, Kunszenti-Kovács – Lovász – Szegedy, Backhausz – Szegedy), which interestingly lead to limit objects that can be viewed as (continuous space) Markov chains with some added features. In other words, the random walk on the graph seems to be the key structure that carries over to the limit.
This observation motivates the goal to see how various results in graph theory carry over to these limit objects. We show that flow theory has a very natural and simple generalization. Counting subgraphs (for example, triangles) is another basic method in graph theory. A generalization of this to the Markov chain setting is not straightforward, but with Kunszenti-Kovács and Szegedy we could develop a theory that covers a good part of graph sequences with intermediate density.
Bio:
László Lovász is a Hungarian mathematician and professor emeritus at Eötvös Loránd University in Budapest. He is best known for his work in combinatorics, discrete optimization and theoretical computer science. In graph theory some of his notable results include the resolution of Kneser’s conjecture, the Lovász Local Lemma, the perfect graph theorem, and designing the (LLL) lattice basis reduction algorithm (with A.K. Lenstra and H.W. Lenstra).
After holding chairs in Szeged and at Eötvös Loránd University he became professor at Yale University in 1993-1999 and a senior researcher at Microsoft Research Center until 2006, when he returned to Eötvös Loránd University. He was president of the International Mathematical Union in 2007-2010 and president of the Hungarian Academy of Sciences in 2014-2020.
Lovász has received numerous awards and prizes, including the 1979 Pólya Prize (SIAM), the 1993 Brouwer Medal (Koninklijk Wiskundig Genootschap), the 1999 Wolf Prize (Israel), the 1999 Knuth Prize (ACM SIGACT), the 2001 Gödel Prize (EATCS and ACM SIGACT), the 2006 John von Neumann Theory Prize (INFORMS), the 2010 Kyoto Prize in Basic Sciences, and the 2021 Abel Prize (from the Norwegian Academy of Sciences and Letters). The Fulkerson Prize (from MOS/SIAM) was awarded to him twice, in 1982 for his work on the ellipsoid method in combinatorial optimization (with M. Grötschel and A. Schrijver), and in 2012 for his work on graph limits (with B. Szegedy). László Lovász became a member of the Royal Netherlands Academy of Sciences in 2006, of the Royal Swedish Academy of Sciences in 2007, of the U.S. National Academy of Sciences and a fellow of the AMS in 2012.
- Dion Gijswijt (Delft University of Technology)
Excluding point configurations over a finite field (presentation)
Abstract:
What is the maximum density of a subset in a finite dimensional space over a finite field that does not contain a given point configuration?
This question, and the analogous question for subsets of the integers, are fundamental in additive combinatorics and have broader implications in combinatorics and theoretical computer science.
The 'cap set problem' corresponds to the configuration of three equally spaced points on a line: a 3-term arithmetic progression. Recently, this problem was solved, showing that the density decreases exponentially in the dimension. This rather unexpected result has led to the development of a new algebraic tool in extremal combinatorics called the slice rank method.
Does a similar exponential decrease occur for *any* given configuration?
This tantalizing open problem is unresolved even for 4-term progressions. In this talk, we will discuss a number of new results towards the solution. In particular, we can show that the density is indeed exponentially small for sufficiently 'nice' excluded configurations.
Bio:
Dion Gijswijt is professor of Discrete Mathematics at Delft University of Technology. He has previously worked at Eötvos-Loránd university, University of Amsterdam, CWI, and Leiden University. He earned his Ph.D. in 2005 from the University of Amsterdam, under supervision of Alexander Schrijver. His main research interests are in discrete mathematics, in particular combinatorial optimisation and extremal combinatorics. For his work on the cap set problem, he received the N.G. de Bruijn prize in 2019. He also contributes to the popularization of mathematics and is involved in the mathematical olympiad.
- Jeroen Zuiddam (University of Amsterdam)
Asymptotic spectrum duality in computer science and discrete mathematics: Matrix multiplication and Shannon capacity (presentation)
Abstract:
In 1969, Strassen shocked the computational world with his sub-cubic algorithm for multiplying matrices. Attempting to understand the best possible algorithm for this problem, Strassen went on to develop his magnificent theory of asymptotic spectra in three papers between 1986–1991.
Strassen’s theory has led to many subsequent results, especially new algorithmic, structural and barrier results for matrix multiplication. Recently, the generality of Strassen’s theory has been applied to the study of a variety of very different settings and parameters in diverse fields that involve "economies of scale" or "direct-sum problems".
In particular we will discuss in this talk how it was applied to give a dual characterisation of the Shannon capacity of graphs, a notion introduced by Shannon in 1956 to model efficient communication over noisy channels, and thus unify important methods in this area (e.g. the Lovász theta function) and obtain new structural results.
Bio:
Jeroen Zuiddam is a mathematician and computer scientist working on various topics in computational complexity theory, quantum information theory and discrete mathematics. Since 2021 he is an assistant professor at the Korteweg-de Vries Institute for Mathematics of the University of Amsterdam.
Zuiddam obtained his PhD cum laude at CWI and the University of Amsterdam in 2018, under supervision of Harry Buhrman. From 2018 to 2020 he was a postdoctoral member of the School of Mathematics at the Institute for Advanced Study in Princeton, hosted by Avi Wigderson. From 2020 to 2021 he was a Simons Junior Fellow at the Courant Institute of Mathematical Sciences of New York University, hosted by Oded Regev. He was awarded a 2021 Veni grant by the Dutch Research Council NWO.
- Avi Wigderson (Institute for Advanced Study, Princeton)
The Value of Errors in Proofs (a fascinating journey from Turing's 1936 seminal R ≠ RE to the 2020 breakthrough of MIP* = RE) (presentation)
Abstract:
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 here https://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.
Bio:
Avi Wigderson is Professor at the School of Mathematics at the Institute of Advanced Study in Princeton, New Jersey. His research interests include Randomness and Computation, Algorithms and Optimization, Complexity Theory, Circuit Complexity, Proof Complexity, Quantum Computation and Communication, Cryptography and Distributed Computation. He has received numerous awards and prizes, including the 1994 Nevanlinna Prize (from IMU), the 2008 Conant Prize (from AMS), the 2009 Gödel Prize (from EATCS and ACM-SIGACT), the 2019 Knuth Prize (from ACM-SIGACT), and the 2021 Abel Prize (from the Norwegian Academy of Science and Letters). He became a member of the American Academy of Arts and Sciences in 2009, a member of the National Academy of Sciences in 2011, an ACM fellow in 2018, and a member of the Norwegian Academy of Sciences and Letters. In addition he has given a Plenary Lecture at the International Congress of Mathematicians in 2006 in Madrid.
- Michael Walter (University of Amsterdam, Ruhr-University Bochum)
Symmetries of Computational Problems and Optimization (presentation)
Abstract:
Many computational problems are invariant under symmetries. Revealing them can be an essential tool to obtain structural insight and find fast algorithms. We will give an introduction to these connections, which are rooted in invariant theory, survey some applications from statistics to quantum information, and sketch how optimization in curved spaces, which arise naturally from the often noncommutative symmetries, has recently led to significant progress. This talk is based on joint works with Peter Bürgisser, Cole Franks, Ankit Garg, Visu Makam, Harold Nieuwboer, Rafael Oliveira, and Avi Wigderson.
Bio:
Michael Walter is an Assistant Professor at the University of Amsterdam and from January 2022 a Professor of Quantum Information at Ruhr-University Bochum. He has previously worked at Stanford University and ETH Zürich. His research interests are in quantum information and computation and their interplay with mathematics, computer science, and theoretical physics. For his work he received an Early Career Award of the Royal Netherlands Academy of Arts and Sciences in 2020.
