The 4th Annual Minisymposium on Computational Topology

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.

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

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.

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.

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.

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.