• Applied and Computational Algebraic Topology
• Conference

• Schedule
• Participants

I will discuss the efficient computation of the Vietoris–Rips persistence barcode for a finite metric space. The implementation in the newly developed C++ code "Ripser" focuses on memory and time efficiency, outperforming previous software by a factor of more than 40 in computation time and a factor of more than 15 in memory efficiency on typical benchmark examples. The improved computational efficiency is based on a close connection between persistent homology and discrete Morse theory, together with novel algorithmic design principles, avoiding the explicit construction of the filtration boundary matrix.

Recorded Talk

Simplicial complex describe a large variety of complex interacting systems ranging from brain networks, to social and collaboration networks. Additionally simplicial complexes have a geometrical interpretation and for this reasons they have been widely used in quantum gravity. Simplicial complexes are the ideal structures to characterize emergent network geometry in which geometrical properties of the networks emerge spontaneously from their dynamics. Here we propose a general model for growing simplicial complexes called network geometry with flavor (NGF). This model deepens our understanding of growing complex networks and reveals the important effect that the dimensionality of growing simplicial complexes have on their evolution. The NGF can generate discrete geometries of different nature, ranging from chains and higher dimensional manifolds to scale-free networks with small-world properties, scale-free degree distribution and non-trivial community structure. Interestingly the NGF with fitness of the nodes reveals relevant relations with quantum statistics. Finally these networks evolving by a purely combinatorial rule display an emerging hyperbolic geometry defining a clear roadmap for emergent geometry.

Recorded Talk

We develop a geometric framework that characterizes the synchronization problem – the problem of consistently registering or aligning a collection of objects. We formulate a theory that characterizes the cohomological nature of synchronization based on the classical theory of fibre bundles. We first establish the correspondence between synchronization problems in a topological group G over a connected graph Γ and the moduli space of flat principal G-bundles over Γ, and develop a discrete analogue of a well-known theorem on classification of flat principal bundles with a fixed base and structural group. In particular, we show that prescribing an edge potential on a graph is equivalent to specifying an equivalence class of flat principal bundles, and we show that the existence of a solution to the synchronization problem is determined by the triviality of holonomy. We then develop a twisted cohomology theory for associated vector bundles arising from an edge potential, which is a discrete version of the twisted cohomology in differential geometry. This theory realizes the obstruction to synchronizability as a cohomology group of the twisted de Rham cochain complex. We then build a discrete twisted Hodge theory – a fibre bundle analog of the discrete Hodge theory on graphs – which geometrically realizes the graph connection Laplacian as a Hodge Laplacian of degree zero. Motivated by our geometric framework, we study the problem of learning group actions – partitioning a collection of objects based on the local synchronizability of pairwise correspondence relations. A dual interpretation is to learn finitely generated subgroups of an ambient transformation group from noisy observed group elements. A synchronization-based algorithm is also provided, and we demonstrate its efficacy using simulations and real data. This talk is based on joint work with Sayan Mukherjee and Tingran Gao.

Recorded Talk

Certain items of persistent homology computations are of particular interest to practitioners but are unfortunately unstable. For a notorious example, consider the generating cycle of a particular point in the persistence diagram. I will present a general framework for providing stable versions of such calculations. This is joint work with Paul Bendich and Alexander Wagner.

Recorded Talk
Slides

In cardiac image analysis, it is important yet challenging to reconstruct the trabeculae, namely, fine muscle columns whose ends are attached to the ventricular walls. To extract these fine structures, traditional image segmentation methods are insufficient. We propose to detect salient topological handles based on persistent homology. Furthermore, we propose to compute the optimal representations of these handles. To this end, we propose a general-purpose algorithm that efficiently computes the shortest representative cycle of a persistence dot. We validate our contribution by comparing with previous standard segmentation methods without topological priors, as well as topological method without the optimal representations.

Recorded Talk

We introduced a notion of directed homology, called natural homology, based on the idea that trace spaces and their evolution with time are what matters. The crucial point was that this homology, defined as diagrams with values in modules, i.e., functors from some small category to a category of modules, must not be compared up-to isomorphisms (which is too fine-grained) but up-to some kind of bisimulations, based on the work of Joyal et al.: what matters again is not the fact that directed spaces have exactly the same kind of trace spaces, but that they have the same kind of "evolution" of trace spaces.

In this talk, I give an overview of the main properties of this directed homology based on classical properties of singular homology, more particularly:

• computability, i.e., it is possible in some cases to compute a finite diagram equivalent to our homology, and decide their bisimilarity,
• some form of exactness, based on Grandis' work on non-Abelian theories,
• dihomotopy invariance, i.e., natural homology is invariant of natural homotopy, but also of a notion of dihomotopy equivalence, called inessential equivalence.

Joint work with Eric Goubault and Jean Goubault-Larrecq.

Recorded Talk

Directed topological spaces were introduced as a model for concurrent computing. The set of directed structures on a given space form a Heyting algebra. We give an overview of this way of discussing directed structures. In the end, we take a detour to TDA and give a short introduction to the Accumulated Persistence Function defined by J. Møller and C.A.N. Biscio.

Recorded Talk

Motivated by applications in road network analysis, the large scale structure of the Universe, and prostate cancer histology, we will explore how persistent homology and its derivitives can be used as topological descriptors of data. We will explore how to use these descriptors in statistical settings, such as hypothesis testing.

The most useful models for understanding these computations in (real or artificial) neural networks tend to have a distinctly topological flavor, including features like qualitative notions of similarity and difference, rather than intrinsic metrics, or of reconstructing global signals from local measurements. In fact, recent experiments have shown that this is not an accident: fundamental systems like the hippocampus encode topological, rather than geometric, features of the environment. Further, the architecture of the network must intrinsically contain information about the computation is it to perform, so it is sensible to expect that topological methods can help us understand the structure/function relationship. Here, we apply tools from classical and algebraic topology to constrain the possible structure of a neural network (or the data it encodes) from observations of its activity.

Recorded Talk

In this work, we extend the topology-based approach for characterizing computability in asynchronous crash-failure distributed systems to asynchronous Byzantine systems. We give necessary and sufficient conditions to solve arbitrary tasks in asynchronous Byzantine systems where an adversary chooses faulty processes. In our adversarial formulation, outputs of non-faulty processes are constrained in terms of inputs of non-faulty processes only. For colorless tasks, an important subclass of distributed problems, the general result reduces to a model that effectively captures the relation between the number of processes, the number of failures, as well as the topological structure of the task's simplicial complexes.

Joint work with Hammurabi Mendes.

Recorded Talk

In this talk, I will present a recent result about convergence of persistence diagrams on stationary point processes in R^N. Several limit theorems such as strong laws of large numbers and central limit theorems for random cubical homology are also shown. If I have time, recent progress on higher dimensional generalization of Frieze zeta function theorem is also presented.

Recorded Talk

The computational pipeline of topological data analysis consists of three major steps:
(1) Deriving a multi-scale representation of the underlying data set
(2) Computing topological invariants of that representation
(3) Interpreting the outcome of (2) to draw conclusions about the data

In my talk, I will present new results in all three steps. In particular,
@(1) an approximation scheme for Rips and Cech complexes in high dimensions,
@(2) an algorithm to compute persistence diagrams of sequences of general simplicial maps,
@(3) an efficient implementation for computing Bottleneck and Wasserstein distances of peristence diagrams.

These results are joint work with Aruni Choudhary, Dmitriy Morozov, Arnur Nigmetov, Sharath Raghvendra and Hannah Schreiber.

Recorded Talk

Under very general assumptions, statistical unbiasedness of a Bayesian model maximizes its predictive power. The model is unbiased if it satisfies the maximum-entropy requirement, meaning that the entropy of the probability distribution defined by the model is maximized subject to a set of constraints that usually correspond to properties of real data that one wishes to model. Exponential random graph models is a classic example of this approach in random graphs/statistics: Erdos-Renyi random graphs are maximum-entropy random graphs with a given expected average degree, for instance. Given that random simplicial complexes have recently attracted increasing interest in modeling real complex systems, we initiate the study of random simplicial complexes from the statistical perspective, focusing on the maximum-entropy principle.

We show that a very general class of random simplicial complexes in which all simplices, of any dimension, are independent Bernoulli random variables, with generally different success probabilities, are maximum-entropy ensembles. Quite surprisingly, we find that as opposed to exponential random graphs with independent Bernoulli edges, in random simplicial complexes with independent Bernoulli simplices there are two types of constraints in the corresponding maximum-entropy ensembles. The constraints of the first type fix the expected numbers of simplices of different dimension as expected, while the constraints of the second type fix the expected numbers of their boundaries. The constructive definition of exponential random simplicial complexes in which only the constraints of the first type are enacted remains an interesting open problem.

The Sum Complex X_A,k associated with a subset A of the cyclic group Z_n and an integer 1 ≤ k ≤ n is the (k-1)-dimensional simplicial complex on the vertex set Z_n whose maximal simplices are the sets σ ⊂ Z_n of cardinality k such that ∑_x∈σ x ∈ A. Sum complexes may be viewed as high dimensional analogues of Cayley graphs over Z_n and are relevant to a number of problems in topological combinatorics. In this talk, we will describe the homology of sum complexes as well as some of their applications, including:
1. Construction of high dimensional trees from sum complexes.
2. Upper bounds on Betti numbers in terms of links, and nearly matching lower bounds via sum complexes.
3. Uncertainty inequalities for the finite Fourier transform and their connections to the topology of sum complexes.

The talk is based in parts on joint work with Nati Linial and Mishael Rosenthal and with Amir Abu-Fraiha.

Recorded Talk

Time varying observations are ubiquitous in today's data rich world; examples include real-valued time series, video data, dynamic networks, etc. Recently, there has been considerable effort combining techniques from nonlinear time series analysis and computational topology in order to generate topological summaries describing the dynamics underlying these systems. In order to leverage these topological features for learning purposes, we will describe theoretical results characterizing compactness in the space of persistence diagrams (bottleneck distance), and present a Weierstrass approximation type theorem for compactly supported functions on the space of persistence diagrams. Several novel applications will be presented.

The usual epistemic S5 model for multi-agent systems is a Kripke graph, whose edges are labeled with the agents that do not distinguish between two states. We propose to uncover the higher dimensional information implicit in the Kripke graph, by using as a model its dual, a chromatic simplicial complex. For each state of the Kripke model there is a facet in the complex, with one vertex per agent. If an edge (u,v) is labeled with a set of agents S, the facets corresponding to u and v intersect in a simplex consisting of one vertex for each agent of S. Then we use dynamic epistemic logic to study how the simplicial complex epistemic model changes after the agents communicate with each other. There are known topological invariants preserved from the initial epistemic complex to the epistemic complex after an action model is applied, that depend on how reliable the communication is. In turn these topological properties determine the knowledge that the agents may gain after the communication happens, to solve a given distributed task, also modeled using dynamic epistemic logic.

Joint work with Eric Goubault.

Recorded Talk

Starting from a Poisson point process in d-dimensional Euclidean space we construct the Rips-Vietoris and the Cech complex. We are interested in concentration inequalities for the number of k-dimensional simplices or more general subgraph counts. This gives rise to concentration inequalities for component counts. In the last part of the talk we investigate the Betti numbers of components of these simplicial complexes.

Recorded Talk

In statistical shape analysis we want methods to quantify how different two shapes are. In this talk I will outline a method using the topological tool of persistent homology. I will define the Persistent Homology Transform, which consists of a family of persistence diagrams constructed from height functions in different directions. This transform is injective, stable, and can effectively describe geometrical features without the use of landmarks. The talk will end with a variety of example applications.

Recorded Talk

Understanding high dimensional data remains a challenging problem. Topological Data Analysis (TDA) promises to simplify, characterize and compare such data. However, standard TDA focuses on Euclidean spaces, while many types of high-dimensional data naturally live in non-Euclidean ones. Spaces derived from text, speech, image, … data are best characterized by non-metric dissimilarities, many of which are inspired by information-theoretical concepts. Such spaces will be called information spaces.

I will present the theoretical foundations of topological analysis in information spaces. First, intuition behind basic computational topology methods is given. Then, various dissimilarity measures are defined along with information theoretical and geometric interpretation. Finally, I will show how the framework of TDA can be extended to information spaces. In particular, I will explain to what extent existing software packages can be adapted to this new setting.

This is joint work with Herbert Edelsbrunner and Ziga Virk.

Algebraic topology was revolutionized by the introduction of spectral sequence methods. As a result our knowledge far outstrips our understanding. I will try to explore some function spaces using persistence homology of the lipschitz functional and via other geometric measurements.

Recorded Talk

Higher Dimensional Automaton is a cubical complex with two distinguished vertices: the initial and the final state and some labeling of vertices. Higher Dimensional Automata are used to model concurrent programs; possible states (respectively possible executions) of a given program correspond to points (respectively directed paths) of the geometric realization of the underlying cubical complex.

I will present a construction of a CW-complex which is homotopy equivalent to the space of directed paths on a cubical complex. This construction satisfies certain minimality condition which makes it useful for direct calculations. Furthermore, such CW-complexes carry an interesting combinatorial structure — their cells can be identified with products of permutohedra and attaching maps are inclusions of faces. I will also discuss the relationship of this construction with other models of directed path spaces.

Recorded Talk