• Applied and Computational Algebraic Topology
• Spring School

• Schedule
• Participants

Persistent homology, the homology of a filtration, is described up to isomorphism by the persistence diagram (barcode), which encodes the structure of its indecomposable summands. A fundamental theorem states that small changes in the input data lead only to small changes in the persistence barcode. We will study a constructive algebraic approach to this result that admits a high level of generality.

Slides

Recorded Talk

Functions of many variables may be very complex. And optimizing them can be excedingly difficult or slow.

Think for instance of the following simple question: How hard is it to find the minimum of a cubic polynomial of many variables? If you chose the cubic polynomial randomly, it is very hard.

I will survey recent work describing this phenomenon and its consequences, first from a geometric point of view, and introduce an important topological phase transition. I will illustrate this phenomenon first in the case of random functions on the high-dimensional sphere. These random functions happen to be the energy landscapes of important models of statistical physics of disordered media, i.e spherical spin glasses. I will then show how this could be extended to more general models of random functions, and in particular for the random landscapes of statistics of large data sets, and for instance of deep learning algorithms, which are at the heart of many of the recent progress in Data Science. The common mathematical field underlying these different questions is given by Random Matrix Theory, through the classical tool of random geometry, i.e. the Kac-Rice formulae.

The relevant work is joint with mathematical colleagues (Auffinger, Cerny, Jagannath, Subag, Zeitouni) or physicists (Biroli, Cammarota, Fyodorov and Khorunzenko) and Computer Scientists (Yann Le Cun and his team at Facebook).

From the brain to the Internet most complex systems can be represented by their underlying network structure. In the last twenty years the field of network theory has provided a general framework to understand the interplay between network topology and dynamics.

In this lecture we will give a general overview on equilibrium maximum entropy ensembles and non equilibrium grow models to characterize complex network topologies.

Finally we will discuss recent developments of the field presenting novel approaches for modelling complex simplicial complexes, describing systems ranging from brain networks to social collaboration networks.

Slides

Recorded Talk

Topological Data Analysis (TDA) is a recent and fast growing field that is mainly motivated by the idea that topology and geometry provide a powerful approach to infer, analyze and exploit robust qualitative and quantitative information about the structure of data represented, in general, as point clouds or samples in Euclidean or more general metric spaces.

An important goal of TDA is to study and ensure the relevance of the topological information inferred from data. From a mathematical perspective, this relevance is expressed as stability properties of the computed topological invariants with respect to various sampling conditions.

The goal of the two talks will be to present a few deterministic and statistical techniques and results leading to such stability properties. The first talk will be dedicated to geometric inference and stability properties of persistent homology in a deterministic setting. In the second talk, we will consider statistical aspects of persistent homology in the TDA pipeline and we will show how statistical approaches can be used to overcome computational and noise issues in the TDA pipeline.

I will discuss various models producing large random spaces (simplicial complexes and closed manifolds). The main goal is to analyse properties which hold with probability tending to one in various regimes. Our focus will be on Betti numbers and on the fundamental group (its geometric and cohomological dimension, torsion etc). I shall also discuss probabilistic version of the Whitehead Conjecture.

Slides

Recorded Talk

We shall talk about various simplicial models for distributed computing. The main model consists of iterated chromatic subdivisions and corresponds to the well-used model in distributed computing. Using the Weak Symmetry Breaking as an example we shall translate questions of distributed computing into purely combinatorial-simplicial questions for the corresponding complex. We shall see how this approach leads to many interesting new and open questions in various fields of mathematics.

Slides

Recorded Talk, part 1

Recorded Talk, part 2

Models and techniques borrowed from classical combinatorial algebraic topology have yielded a variety of new lower bounds and impossibility results for distributed and concurrent computation. We will explain the basic concepts underlying this approach, and show how they apply to a simple distributed problem.

Slides

Recorded Talk

Stochastic Geometry deals with mathematical models for random geometric structures and spatial data, as they arise in many applications. These include the analysis of porous media, packings of solid bodies, biological tissues, soft matter (foams), structures encountered in various branches of physics or telecommunication networks …

The aim of this presentation is to provide an introduction to some of the basic models of stochastic geometry and to indicate the underlying mathematical framework. These models and concepts include

• random closed sets,
• point processes,
• particle processes,
• Boolean models,
• random mosaics.

We also briefly introduce some geometric characteristics and their properties, which have been crucial for exploring random structures and which hopefully will be complemented and enhanced by new descriptors from computational topology, in the future.

Slides

Spatial point processes are a central theme in stochastic geometry and spatial statistics. In our previous presentation, we already encountered some concepts, results and examples related to point processes in a geometric context. We now provide further background information and examples of point processes such as (again) Poisson processes, Cox processes, cluster processes, permanental processes and discuss fundamental operations on point processes such as mixing, marking, thinning, transformation or change of density.

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

Each of the three steps comes with its own algorithmic challenges. Obviously, the interest of tda in various applied fields asks for software to handle all these tasks efficiently, generally, and reliably. We will review standard techniques for all three steps, in particular:
@(1) how to generate filtrations of simplicial complexes out of point clouds and scalar fields,
@(2) how to compute persistent homology of a filtration efficiently using matrix reduction,
@(3) how to compare persistent diagrams efficiently.

My conference talk on Tuesday morning will be a continuation on the topic, presenting recent advances on the three steps of the pipeline.

Recorded Video 

A standard way to schematically represent networks in general, and neural network in particular, is as a graph. Depending on context, graphs representing networks can be directed or undirected, and in some cases carry labels or weights on their vertices and edges. With any graph one can associate a variety of combinatorial and topological objects, as well as certain algebraic invariants. The problem in using such ideas in neuroscience has been that obtaining connectivity data from a biological brain is very hard and expensive with existing techniques. Hence only very small connectivity patterns are understood, and extracting meaningful topological structures is not likely. Artificial neural networks, created by probabilistic rules can give much larger graphs, but they only provide a partial solution, as with existing knowledge their connectivity and functionality is not capable of reliably reproducing biological neuronal networks.

In this talk I will survey an on-going collaborative project where we apply topological techniques and ideas to the study of the brain. The project was motivated by the creation of a biologically accurate digital reconstruction of a small part of the cortex of a young rat by the Blue Brain Project. This digital model provided a way of extracting very accurate structural and functional information. Hence it allows us to extract large directed structural connectivity graphs that are a good approximation to the connectivity in a biological tissue. We have also developed ways of extracting time series of graphs corresponding to the reaction of the system to a variety of stimuli. These directed graphs can be studied using a combination of novel ideas and basic algebraic topology. I will describe some of our methods and the results obtained by applying them to the Blue Brain reconstruction.

Slides

Recorded Talk

Expander graphs have been a focus of intensive research in the last four decades, with numerous applications throughout mathematics and theoretical computer science. In view of the ubiquity of expander graphs, there a recent growing interest in high dimensional notions of expansion. We will discuss two such notions. The first is a k-dimensional version of the graphical Cheeger constant, called "coboundary expansion", that came up independently in joint work with Linial and Wallach on homological connectivity of random complexes and in Gromov's remarkable work on the topological overlap property. The second notion is called "spectral expansion" and is quantified via the minimal eigenvalue of the k-dimensional Laplacian operator acting on the space of real valued k-cochains of the complex. While these two notions are essentially equivalent in the graphical k=1 case, they are substantially different in dimensions k>1.

We will survey different aspects of both notions of expansion, including in particular questions of existence and construction of high dimensional expanders, estimates of the expansion of some commonly occurring complexes, and combinatorial and geometric consequences of expansion.

Slides

Recorded Talk

Concurrent programs use multiple computing resources in parallel in order to compute efficiently. Their study is notoriously difficult because one has to take in account all their possible executions, i.e. all the possible ways the instructions of the processes may be interleaved, but fortunately many of these executions are equivalent because they differ only by inessential reordering of instructions. Thus, the space consisting of all the possible states the program, as well as the possible commutations between instructions, is here the main object of interest. We will see that it is most naturally described as a precubical set and can be studied from a geometric point of view. I will present here the basic definitions and explain some geometric features of the spaces obtained in this way. In particular, they are equipped with a notion of direction (of time), which requires to adapt most usual geometric concepts and invariants.

Slides

Recorded Talk #1

Recorded Talk #2

Concurrency theory in Computer Science studies effects that arise when several processors run simultaneously sharing common resources. It attempts to advise methods dealing with the "state space explosion problem" characterized by an exponentially growing number of execution paths; sometimes using models with a combinatorial/topological flavor. It is a common feature of these models that an execution corresponds to a directed path (d-path) in a (time-flow directed) state space, and that d-homotopies (preserving the directions) have equivalent computations as a result.

Getting to grips with the effects of the non-reversible time-flow is essential, and one needs to "twist" methods from ordinary algebraic topology in order to make them applicable. An essential task consists in inferring information about spaces of executions (directed paths) between two given states from information about the state space. The determination of path components is particularly important for applications.

I will discuss particular directed spaces arising from Higher Dimensional Automata (HDA). There are various methods identifying the homotopy type of the space of executions between two states in such an automaton with some finite complex: in simple cases as prodsimplicial complex – with products of simplices as building blocks – or as a configuration space living in a product of simplices. In several interesting cases, it is possible to give an explicit description of the homotopy type of the Alexander dual of such a configuration space and hence of the stable homotopy type of the corresponding trace space. This opens up for calculations of homology groups and of other topological invariants of some execution spaces.

We sketch a method recently devised by Ziemiański identifying – for a general HDA – a space of directed paths with a prodpermutahedral complex arising by glueing various permutahedra along their boundaries.

Joint work with L. Fajstrup (Aalborg), E. Goubault, E. Haucourt, S. Mimram (Éc. Polytechnique, Paris), R. Meshulam (Haifa) and K. Ziemiański (Warsaw).

Slides

Recorded Talk