9th Annual Minisymposium on Computational Topology

Part of Computational Geometry Week (CG Week 2021)

Buffalo, New York, online, June 8 and June 10, 2021

Overview

The Workshop

Computational topology is an emerging field that brings together researchers from computational geometry, algebraic, geometric, and low-dimensional topology, data science, and many other related scientific areas. One important driving force are applications of topological ideas and methods in data analysis, which have opened up new opportunities. Another impetus has been the interplay with the closely connected areas of topological combinatorics and quantitative topology, which share many tools and methods; this has been extremely fruitful and led to a number of new advances. This workshop is intended to bring together researchers working in applied, computational, and quantitative topology and topological combinatorics, and to foster further exchange of ideas.

Confirmed Invited Speakers

Dominique Attali (CNRS, Gipsa-lab)
Benjamin Burton (University of Queensland)
Marc Lackenby (Oxford)
Fedor Manin (UCSB)
Elizabeth Munch (Michigan State University)
Yuval Peled (Courant Institute, NYU)
Érika Roldán (TU München)
Raphaël Tinarrage (FGV EMAp)

Format

The workshop will span two half days. Each half-day consists of four 45-minute presentations, including five minutes for questions. There is a ten-minute break in the middle of each half-day.

Intended Audience

Besides people working in the field of computational topology, the workshop is targeted at researchers from computational geometry, data analysis, machine learning, and statistics, who want to learn about recent developments in the area.

Schedule

Schedule

Tuesday, June 8, 2021
Time (EDT) Speaker Title
1:20pm-2:05pm Raphaël Tinarrage
2:05pm-2:50pm Erika Roldan
2:50pm-3:00pm Break
3:00m-3:45pm Fedor Manin
3:45pm - 4:30pm Yuval Peled
Thursday, June 10, 2021
Time (EDT) Speaker Title
1:20pm-2:05pm Benjamin Burton
2:05pm-2:50pm Marc Lackenby
2:50pm-3:00pm Break
3:00m-3:45pm Elizabeth Munch
3:45pm - 4:30pm Dominique Attali

Abstracts

Simplicial approximation to CW-complexes in practice

Raphaël Tinarrage

It is known that any topological manifold is homotopy equivalent to a CW-complex, and that any CW-complex is homotopy equivalent to a simplicial complex. Despite this fact, only a few of these simplicial complexes are available in practice. A striking example is given by the Grassmannians of d-planes in R^n, with 1< d < n, for which homotopy equivalent simplicial complexes are explicitly known only when d is 1 or n-1. I will describe an implementation of an algorithm that takes as an input a CW complex and returns a simplicial complex of same homotopy type. This algorithm, though well-known in the literature, requires some work to make it computationally tractable. A close attention is paid to triangulations of mapping cones, generalized subdivisions and weak simplicial approximations. I will illustrate the algorithm with the real projective spaces, the 3-dimensional lens spaces and the Grassmannian of 2-planes in R^4.

Topology and Geometry of Random Polyominoes

Erika Roldan

Do you know what algorithm is deciding which piece you get next in a Tetris game? In this talk I will start by answering this question and then I will tell you about several different ways of sampling random polyominoes (polyominoes are like tetrominoes but with any desired amount of squares). We will also analyze how the topological and geometric properties of polyominoes change depending on the distribution that we choose to sample them.

Rational homotopy theory and decidability of the extension problem

Fedor Manin

Given a finite simplicial pair (X, A), a finite simplicial complex Y, and a map f:A -> Y, does f extend to X? I will describe the set of situations in which this question is algorithmically decidable, and discuss when it's possible to compute the set of extensions. This generalizes work of Čadek, Krčál, Matoušek, Vokřínek, and Wagner. As an application, the set of isomorphism classes of vector bundle structures over any X with structure group G is computable. Slides

Minimum weight disk triangulations and fillings

Yuval Peled

We study the minimum total weight of a disk triangulation using any number of vertices out of {1,..,n} where the boundary is fixed and the $n \choose 3$ triangles have independent uniform (0,1) weights. We show that, with high probability, the minimum weight is equal to $(c+o(1))n^{-1/2}\log n$ for an explicit constant $c$. Further, we prove that, with high probability, the minimum weights of a homological filling and a homotopical filling of the cycle (123) are both attained by the minimum weight disk triangulation. We will discuss a related open problem concerning simple-connectivity of random simplicial complexes, where a similar phenomenon is conjectured to hold. Bases on joint works with Itai Benjamini, Eyal Lubetzky, and Zur Luria.

High-performance computing with knots, 3-manifolds and 4-manifolds

Ben Burton

Mathematical software is nowadays a common part of the topologist’s toolkit, and the landscape of available software has become significantly broader and more mature over the past few decades. In this talk we move beyond the desktop and onto the supercomputer - there are very different problems to consider when you are solving not just one ad-hoc problem but millions of problems, or when your problem has space or time requirements that far exceed a typical desktop machine. We will work through a variety of difficult topological problems and discuss issues such as parallelism of topological algorithms, exactness and reliability, managing enormous space consumption, and the independent verification of results. The tools will come not just from topology and software engineering, but also combinatorial geometry and graph theory.

Unknot recognition in quasi-polynomial time

Marc Lackenby

I will outline a new algorithm for unknot recognition that runs in quasi-polynomial time. The input is a diagram of a knot with n crossings, and the running time is 2^{O((log n)^3)}. The algorithm uses hierarchies, normal surfaces and Heegaard splittings.

The Directional Transform: From Theory to Practice

Elizabeth Munch

The promise of TDA is enshrined in the idea that data is shape and shape is data. This is realized most concretely in the case of encoding the information of embedded shapes, where the directional transform gives a proveable relationship between a given shape and its TDA signature representation. The pipeline for this setup given a shape $X \subseteq \mathbb{R}^d$ goes through the directional transform, which assigns a function $f:_\omega: X \to \R$ for each direction $\omega \in \mathbb{S}^{d-1}$ given by $f_\omega(x) = \langle x, \omega \rangle$. From here, we can compute any number of TDA signatures of interest. In particular, Turner et al showed that returning the persistence diagram for every direction completely encodes the shape itself. In this talk, we will discuss the boundaries of the existing theory and the usefulness of this construction in such diverse applications as analyzing barley seed morphology and differentiating embedded graphs.

Discrete constructions and geometry driven collapses for shape reconstruction

Dominique Attali

In many practical situations, the shape of interest is only known through a finite set of data points. Given as input those data points, it is then natural to try to construct an approximation of the shape that reflects both its geometry and topology. This problem has given rise to many research works in the computational geometry community, motivated by applications to 3D model reconstruction and manifold learning. In this talk, we will survey a certain number of discrete constructions derived from the data points that are homotopy-equivalent to the shape under some reasonable assumptions on the data points distribution. We shall also see that some of those constructions can be connected by sequence of collapses.

Organizers

Ulrich Bauer
Technical University, München
mail AT ulrich-bauer.org

Arnaud de Mesmay
CNRS, Laboratoire d'informatique Gaspard Monge, Université Gustave Eiffel
arnaud.de-mesmay AT univ-eiffel.fr

Uli Wagner
IST Austria
uli AT ist.ac.at

Support

We gratefully acknowledge support of the Laboratoire d'Informatique Gaspard Monge and the Discretization in Geometry and Dynamics project.

Past iterations

8th Annual Minisymposium on Computational Topology (Portland)
7th Annual Minisymposium on Computational Topology (Budapest)
6th Annual Minisymposium on Computational Topology (Brisbane)
5th Annual Minisymposium on Computational Topology (Boston)
4th Annual Minisymposium on Computational Topology (Eindhoven)
Workshop on Computational Topology and Data Analysis (Rio)
Workshop on Computational Topology (Chapel Hill)