Events - January 2022

Title: Traveling Salesman Problems: Approximation Algorithms and Black-Box Reductions

Abstract:

We survey the recent progress on approximation algorithms and integrality ratios for variants of the traveling salesman problem, with a focus on black-box reductions from one problem to another. In particular, we explain recent results for the Path TSP and the Capacitated Vehicle Routing Problem, which are joint works with Vera Traub and Rico Zenklusen and with Jannis Blauth and Vera Traub.

Title: Random Self-reducibility of Ideal-SVP via Arakelov Random Walks

Abstract:

Fixing a number field, the space of all ideal lattices, up to isometry, is naturally an Abelian group, called the *Arakelov class group*. This fact, well known to number theorists, has so far not been explicitly used in the literature on lattice-based cryptography. Remarkably, the Arakelov class group is a combination of two groups that have already led to significant cryptanalytic advances: the class group and the unit torus.

Title: Minimal relations for an algebra inspired by algebraic graph theory

Abstract:

The balanced algebra has two generators, R and L, and its defining relations are that any pair of balanced words commutes. For example, RL and LR are balanced (contain the same number of both generators), so in the balanced algebra, (RL)(LR)=(LR)(RL).

Title: Enumerating Matroids and Linear Spaces

Abstract:

We show that the number of linear spaces on a set of $n$ points and the number of rank-3 matroids on a ground set of size $n$ are both of the form $(cn+o(n))^{n^2/6}$, where $c=e^{\sqrt 3/2-3}(1+\sqrt 3)/2$. This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: there are exact formulas for enumeration of rank-1 and rank-2 matroids, and it was recently proved by van der Hofstad, Pendavingh, and van der Pol that for constant $r\ge 4$ there are $(e^{1-r}n+o(n))^{n^{r-1}/r!}$ rank-$r$ matroids on a ground set of size $n$.

Title: Crystal invariant theory and geometric RSK

Abstract:

The original problem of classical invariant theory was to describe the invariants of SL_m acting on a polynomial ring in an m \times n matrix of variables. One way to solve this problem is to consider the polynomial ring as a GL_m \times GL_n representation, and decompose this representation into its irreducible components.

Title: Edge-Disjoint Linkage in Infinite Graphs

Abstract:

In 1980 Thomassen conjectured that, for odd k, an edge-connectivity of k is enough for a graph to be weakly k-linked, meaning any k pairs of terminals can be linked by k edge-disjoint paths. The best known result to date for finite graphs is from 1991, by Andreas Huck, and assumes an edge-connectivity of k+1 for odd k.