The 4th Annual Minisymposium on Computational Topology

The minisymposium consists of three workshops:

From Computational Geometry to Topology (Mon 14:00–18:00)

We will have a collection of invited talks emphasizing the connection of geometry and topology. At the end of the workshop, we will run an open problem session (30 minutes) on problems in computational topology, in particular with a connection to geometric problems.


14:00Jeff Erickson
A Brief Pre-History of Computational Topology [+]
Computational issues have been central to topology since its inception more than 250 years ago. This talk will be a brief, sketchy, and biased historical survey of the early evolution of computational topology, starting with the seminal contributions of Descartes, Leibniz, Euler, Gauss, Listing, Möbius, Jordan, Poincaré, Hilbert, Dehn and others, and continuing as far into the 20th century as time allows.
14:30Magnus Botnan
Approximating Persistent Homology in Euclidean Space [+]
A problem often encountered in the computation of persistent homology is that the number of simplices grows too fast in the number of input points and therefore hinders computation up to the desired scale. In this talk I will discuss how the geometry of Euclidean space can be utilized to build memory-efficient approximations of persistent homology. This is joint work with Gard Spreemann.
15:00Benjamin A. Burton
Practical parameterised complexity for knots and 3-manifolds [+]

Exact computation with knots and 3-manifolds is challenging - many fundamental problems are decidable but enormously complex, and it is still unknown whether even “simple” problems such as unknot recognition and 3-sphere recognition can be solved in polynomial time. In this setting, parameterised complexity is emerging as a framework for understanding why, despite these apparent difficulties, modern software packages such as SnapPy and Regina can solve many complex topological problems that “should” be intractable.

Moreover, it is becoming clear that parameterised complexity has an important role to play not just in theory, but also in practice. Fixed-parameter tractable algorithms in computational topology are now being implemented in real software, and are outperforming the prior state-of-the-art algorithms for questions ranging through geometric, algebraic and combinatorial concerns. In this talk we give an overview of the rise of parameterised complexity as a practical tool, and discuss the interplay between combinatorics and topology that makes this possible.

Includes joint work with Clément Maria, William Pettersson and Jonathan Spreer.

15:30Coffee Break
16:00Tamal Dey
Parameter-Free (Friendly?) Topology Inference Through Sparsification [+]

In topological inference from point data, a simplicial complex such as Vietoris-Rips is built on top of the data to carry out the topological analysis. This requires a user-supplied global parameter, which in some cases may be impossible to determine for the purpose of correct topology inference. We show that when the underlying space is a smooth manifold of known dimension embedded in an Euclidean space, a parameter-free sparsification of the data leads to a correct homology inference. This follows from the fact that we can compute a function called lean-set feature size over the data points with which it can be made locally uniform. The construction of the Vietoris-Rips complex on such data can be done adaptively without requiring any user-supplied parameter from which homology of the hidden manifold can be inferred. Preliminary experiments suggest that the strategy achieves correct topological (homology) inference with effective sparsification in practice.

Joint work with Zhe Dong and Yusu Wang

16:30Clément Maria
Zigzag Persistence via Reflections and Transpositions [+]

In this talk, we introduce a new algorithm for computing zigzag persistence, designed in the same spirit as the standard persistence algorithm. Our algorithm reduces a single matrix, maintains an explicit set of chains encoding the persistent homology of the current zigzag, and updates it under simplex insertions and removals. The total worst-case running time matches the usual cubic bound. A noticeable difference with the standard persistence algorithm is that we do not insert or remove new simplices "at the end" of the zigzag, but rather "in the middle". To do so, we use arrow reflections and transpositions, in the same spirit as reflection functors in quiver theory. Our analysis introduces new kinds of reflections in quiver representation theory: the "injective and surjective diamonds". It also introduces the "transposition diamond" which models arrow transpositions. For each type of diamond we are able to predict the changes in the interval decomposition and associated compatible bases. Arrow transpositions have been studied previously in the context of standard persistent homology, and we extend the study to the context of zigzag persistence. For both types of transformations, we provide simple procedures to update the interval decomposition and associated compatible homology basis.

Join work with Steve Oudot.

17:00Open Problems Session

Statistical Approaches to Topological Data Analysis (Tue 14:00–18:00)

The first half of this workshop will consist of an introductory talk and a one-hour tutorial on the R package TDA, led by Brittany Terese Fasy and Jisu Kim. The second half of this workshop will consist of invited talks demonstrating applications of topological data analysis. These talks will be given by Steven P. Ellis, Ellen Gasparovic, Giseon Heo. and Lori Ziegelmeier.


14:00Brittany Terese Fasy
Statistical Approaches to Topological Data Analysis
14:15Jisu Kim
Tutorial on the R Package TDA
Tutorial Handout (PDF)
15:30Coffee Break
16:00Steven P. Ellis
Describing High-Order Statistical Dependence Using "concurrence topology", with Application to Functional MRI Brain Data [+]

In multivariate data analysis dependence beyond pair-wise can be important. With many variables, however, the number of simple summaries of even third-order dependence can be unmanageably large.

``Concurrence topology'' is an apparently new method for describing high-order dependence among up to dozens of dichotomous (i.e., binary) variables (e.g., seventh-order dependence in 32 variables). This method generally produces summaries of dependence of manageable size. (But computing time can be lengthy.) For time series, this method can be applied in both the time and Fourier domains.

Write each observation as a vector of 0's and 1's. A ``concurrence'' is a group of variables all labeled ``1'' in the same observation. The collection of concurrences can be represented as a filtered simplicial complex. Holes in the filtration indicate relatively weak or negative association among the variables. The pattern of the holes in the filtration can be analyzed using persistent homology.

We applied concurrence topology on binarized, resting-state, functional MRI data acquired from patients diagnosed with attention-deficit hyperactivity disorder and from healthy controls. An exploratory analysis finds a number of differences between patients and controls in the topologies of their filtrations, demonstrating that concurrence topology can find high-order structure in data of real-world relevance.

Independence among pairwise disjoint groups of variables is reflected in nontrivial homology cross products of classes in the concurrence homology of the variable groups. In ``canonical concurrence topology'' one looks for nontrivial cross products and interprets that as an indication of ``independence-like'' behavior among the groups of variables.

16:30Ellen Gasparovic
Multi-Scale Local Shape Analysis and Feature Selection in Machine Learning Applications [+]

We introduce a method called multi-scale local shape analysis for extracting features that describe the local structure of points within a dataset. The method uses both geometric and topological features at multiple levels of granularity to capture diverse types of local information for subsequent machine learning algorithms operating on the dataset. Using synthetic and real dataset examples, we demonstrate significant performance improvement of classification algorithms constructed for these datasets with correspondingly augmented features.

This is joint work with Paul Bendich, John Harer, Linda Ness, and Rauf Izmailov.

17:00Giseon Heo
Using Cycles in High Dimensional Data to Analyze Protein Binding [+]
Persistent homology captures the evolution of topological features of a model as a parameter changes. The two standard summary statistics of persistent homology are the barcode and the persistence diagram. A third summary statistic, the persistence landscape, was recently introduced by Bubenik. It is a functional summary, so it is easy to calculate sample means and variances, and it is straightforward to construct various test statistics. Implementing a permutation test we detect conformational changes between closed and open forms of the maltose-binding protein, a large biomolecule consisting of 370 amino acid residues. Furthermore, persistence landscapes can be applied to machine learning methods. A hyperplane from a support vector machine shows the clear separation between the closed and open proteins conformations. Moreover, because our approach captures dynamical properties of the protein our results may help in identifying residues susceptible to ligand binding; we show that the majority of active site residues and allosteric pathway residues are located in the vicinity of the most persistent loop in the corresponding filtered Vietoris-Rips complex. This finding was not observed in the classical anisotropic network model.
17:30Lori Ziegelmeier
Persistence Images: An Alternative Persistent Homology Representation [+]
Topological data analysis, namely persistent homology, allows the extraction of coarse topological features from data. While the roots of this tool are deep in algebraic topology, applications of the methods therein are finding broad applications in the scientific community at large. There are two standard representations of persistent homology: barcodes and persistence diagrams, which summarize topological features of data. The space of persistent diagrams can be given a metric structure, enabling certain machine learning techniques to benefit from the features captured in persistence diagrams. We present an alternative representation that ‘vectorizes’ the information of persistent homology, which we refer to as a persistence image. Persistence images allow the use of a wider set of distance measures and enable a broader list of applicable tools from machine learning. We present analysis of a data set consisting of common topological spaces as well as data arising from the linked-twist map, a dynamical system which simulates turbulent mixing.

Sheaves and Categories (Thu 14:00–17:30)

In order to cater to a broad audience, this workshop will begin with an introductory lecture on the basics of category theory and sheaf theory. The remaining portion of the workshop will be dedicated to several 20-30 minute invited talks on current research trends, both pure and applied.


14:00Vin de Silva
Introduction to Categories, Part I: Key Concepts [+]
What are the key ideas that make category theory interesting and worthwhile? I will try to explain some of the following ideas: categories, functors, natural transformations, comma categories, universal constructions, equivalences of categories, adjunctions, representability.
14:45Elizabeth Munch
The Interleaving Distance [+]
The interleaving distance arose as a metric on persistence modules. However, through category theory, this metric can be extended to a large class of functors which represent many useful constructions in applied topology, including Reeb graphs, Reeb spaces, and multidimensional persistence modules. In this talk, we will discuss the current work on the interleaving distance through examples.
15:30Coffee Break
16:00Vin de Silva
Introduction to Categories, Part II: Persistence via Category Theory [+]
Following Liz's presentation on interleaving, I will discuss the theory in a more abstract way. This is joint work with Peter Bubenik and Jonathan Scott.
16:30Primoz Skraba
Topos Theory for Persistence [+]

Persistent (co)homology has been studied from a variety of viewpoints: algorithmic, algebraic, and categorical.

In this talk, I will describe a complementary approach, based on encoding the time-varying nature of the underlying topological space directly at the set level. In classical persistence, this was done by encoding the filtration with the action of a graded ring on the underlying space (multiplication by t in [CZ04]).

One can generalize this by constraining how the topological space may change over time, e.g. in classical persistence it must grow and in zig-zag persistence it may grow and shrink. We call these constraints, the shape of the theory of persistence. Using tools from topos theory, I will describe that if these constraints have a special structure (i.e. they form a Heyting algebra), we can automatically generate a corresponding persistence theory.

No previous knowledge of topos theory is necessary and in addition to definitions and structural properties, aspects such as computation and stability will also be discussed.