Page 61 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 61
INVITED SPEAKERS
Propositional Proof Complexity
Alexander Razborov, razborov@mi-ras.ru
U Chicago, United States, and Steklov Institute, Russian Federation
Propositional proof complexity studies efficient provability of statements that can be expressed
in quantifier-free form, in various proof systems and under various notions of “efficiency”.
Statements of interest come from a variety of sources that, besides traditional combinatorial
principles and other mathematical theorems, include areas like combinatorial optimization,
practical SAT solving and operation research. While many proof systems considered in the
modern proof complexity are still traditional, in the sense that they are Hilbert-style and logic-
based, a considerable amount of attention has been in recent years paid to systems modelling
algebraic and semi-algebraic reasoning, including elementary convex geometry. In this talk I
will attempt to convey some basic ideas underlying this vibrant area, including a necessarily
based sample of illustrating examples.
Subset products and derangements
Aner Shalev, shalev@math.huji.ac.il
Hebrew University of Jerusalem, 91904, Israel
Coauthors: Michael Larsen, Pham Tiep
In the past two decades there has been intense interest in products of subsets in finite groups.
Two important examples are Gowers’ theory of Quasi Random Groups and its applications
by Nikolov, Pyber, Babai and others, and the theory of Approximate Groups and the Product
Theorem of Breuillard-Green-Tao and Pyber-Szabo on growth in finite simple groups of Lie
type of bounded rank, extending Helfgott’s work.
These deep theories yield strong results on products of three subsets (covering, growth).
What can be said about products of two subsets? I will discuss a recent joint work with Michael
Larsen and Pham Tiep on this challenging problem, focusing on products of two normal subsets
of finite simple groups, and deriving a number of applications.
Our main application concerns derangements (namely, fixed-point-free permutations), stud-
ied since the days of Jordan. We show that every element of a sufficiently large finite simple
transitive permutation group is a product of two derangements. Related results and problems
will also be discussed.
The proofs combine group theory, algebraic geometry and representation theory; it applies
the proof by Fulman and Guralnick of the Boston-Shalev conjecture on the proportion of de-
rangements.
Convex integration and synthetic turbulence
László Székelyhidi Jr., szekelyhidi@math.uni-leipzig.de
University of Leipzig, Germany
In the past decade convex integration has been established as a powerful and versatile tech-
nique for the construction of weak solutions of various nonlinear systems of partial differential
equations arising in fluid dynamics, including the Euler and Navier-Stokes equations. The ex-
59
Propositional Proof Complexity
Alexander Razborov, razborov@mi-ras.ru
U Chicago, United States, and Steklov Institute, Russian Federation
Propositional proof complexity studies efficient provability of statements that can be expressed
in quantifier-free form, in various proof systems and under various notions of “efficiency”.
Statements of interest come from a variety of sources that, besides traditional combinatorial
principles and other mathematical theorems, include areas like combinatorial optimization,
practical SAT solving and operation research. While many proof systems considered in the
modern proof complexity are still traditional, in the sense that they are Hilbert-style and logic-
based, a considerable amount of attention has been in recent years paid to systems modelling
algebraic and semi-algebraic reasoning, including elementary convex geometry. In this talk I
will attempt to convey some basic ideas underlying this vibrant area, including a necessarily
based sample of illustrating examples.
Subset products and derangements
Aner Shalev, shalev@math.huji.ac.il
Hebrew University of Jerusalem, 91904, Israel
Coauthors: Michael Larsen, Pham Tiep
In the past two decades there has been intense interest in products of subsets in finite groups.
Two important examples are Gowers’ theory of Quasi Random Groups and its applications
by Nikolov, Pyber, Babai and others, and the theory of Approximate Groups and the Product
Theorem of Breuillard-Green-Tao and Pyber-Szabo on growth in finite simple groups of Lie
type of bounded rank, extending Helfgott’s work.
These deep theories yield strong results on products of three subsets (covering, growth).
What can be said about products of two subsets? I will discuss a recent joint work with Michael
Larsen and Pham Tiep on this challenging problem, focusing on products of two normal subsets
of finite simple groups, and deriving a number of applications.
Our main application concerns derangements (namely, fixed-point-free permutations), stud-
ied since the days of Jordan. We show that every element of a sufficiently large finite simple
transitive permutation group is a product of two derangements. Related results and problems
will also be discussed.
The proofs combine group theory, algebraic geometry and representation theory; it applies
the proof by Fulman and Guralnick of the Boston-Shalev conjecture on the proportion of de-
rangements.
Convex integration and synthetic turbulence
László Székelyhidi Jr., szekelyhidi@math.uni-leipzig.de
University of Leipzig, Germany
In the past decade convex integration has been established as a powerful and versatile tech-
nique for the construction of weak solutions of various nonlinear systems of partial differential
equations arising in fluid dynamics, including the Euler and Navier-Stokes equations. The ex-
59
