Archive

Archive 2021

All recorded talks are available on our YouTube-clannel

Oct 19, 2021
Tuesday
18.00
Moscow
UTC +3
Alan Reid Rice University, USA
The geometry and topology of arithmetic hyperbolic manifolds of simplest type

This talk will survey as well as discuss geometric and topological properties of arithmetic hyperbolic manifolds of simplest type. These are precisely the class of arithmetic hyperbolic manifolds that contain an immersed co-dimension one totally geodesic submanifolds.

10.08.2021
Tuesday
19.00
UTC +3
Alex Scott University of Oxford
Combinatorics in the exterior algebra and the Two Families Theorem

The Two Families Theorem of Bollobas says the following: Let $(A_i,B_i)$ be a sequence of pairs of sets such that the $A_i$ have size a, the $B_i$ have size $b$, and $A_i$ and $B_j$ intersect if and only if $i$ and $j$ are distinct. Then the sequence has length at most $\binom{a+b}{a}$.

This beautiful result has many applications and has been generalized in two distinct ways. The first (which follows from the original result of Bollobas) allows the sets to have different sizes, and replaces the cardinality constraint with a weighted sum. The second uses an elegant exterior algebra argument due to Lovasz and allows the intersection condition to be replaced by a skew intersection condition. However, there are no previous results that have versions of both conditions.

In this talk, we will explain and extend the exterior algebra approach. We investigate the combinatorial structure of subspaces of the exterior algebra of a finite-dimensional real vector space, working in parallel with the extremal combinatorics of hypergraphs. As an application, we prove a new extension of the Two Families Theorem that allows both (some) variation in set sizes and a skew intersection condition.

This is joint work with Elizabeth Wilmer (Oberlin).

Meeting ID: 28846929 zoom-link
Password: in open or as a puzzle
Oct 5, 2021
Tuesday
18.00
Moscow
UTC +3
Alex Lubotzky Hebrew University, Israel
Stability and testability of permutations' equations

Let $A$ and $B$ be two permutations in $\text{Sym}(n)$ that ``almost commute'' -- are they a small deformation of permutations that truly commute? More generally, if $R$ is a system of words-equations in variables $X = \{x_1, \ldots ,x_d\}$ and $A_1, \ldots, A_d$ are permutations that are nearly solutions; are they near true solutions?

It turns out that the answer to this question depends only on the group presented by the generators $X$ and relations $R$. This leads to the notions of ``stable groups'' and ``testable groups''.

We will present a few results and methods which were developed in recent years to check whether a group is stable or testable. We will also describe the connection of this subject with property testing in computer science, with the long-standing problem of whether every group is sofic, and with invariant random subgroups.

17.08.2021
Tuesday
19.00
UTC +3
Avi Wigderson IAS, Princeton
Optimization, Complexity and Math (or, can we prove P ≠ NP using gradient descent)

This talk aims to summarize the status and goals of a broad research project. The main messages of this project are summarized below; I plan to describe, through examples, many of the concepts they refer to, and the evolution of ideas leading to them. No special background is assumed.

  1. We extend some basic algorithms of convex optimization from Euclidean space to the far more general setting of Riemannian manifolds, capturing the symmetries of non-commutative group actions. The main tools for analyzing these algorithms combine central results from invariant and representation theory.
  2. One main motivation for studying these problems and algorithms comes from algebraic complexity theory, especially attempts to separate Valiant’s algebraic analogs of the P and NP. Symmetries and group actions play a key role in these attempts.
  3. The new algorithms give exponential (or better) improvements in run-time for solving algorithmic many specific problems across CS, Math and Physics. In particular, in algebra (testing rational identities in non-commutative variables), in analysis (testing the feasibility and tightness of Brascamp-Lieb inequalities), in quantum information theory (to the quantum marginals problem), optimization (testing membership in “moment polytopes”), and others. This work exposes old and new connections between these diverse areas.
Meeting ID: 28846929 zoom-link
Password: in open or as a puzzle