ICMS

Applied and computational topology: ATMCS 5

Jul 02, 2012 - Jul 06, 2012

ICMS, 15 South College Street Edinburgh

Organisers

Name	Institution
Carlsson, Gunnar	Stanford University
Chazal, Frederic	INRIA Saclay - Île-de-France
Farber, Michael	University of Warwick
Ghrist, Robert	University of Pennsylvania
Jardine, Rick	University of Western Ontario
Mischaikow, Konstantin	Rutgers, State University of New Jersey
Vejdemo-Johansson, Mikael	University of St Andrews

ATMCS 5 is the 5th conference in a conference series on Algebraic Topology, its role in Computer Science, and its applications. The acronym changed interpretation for ATMCS 4 in 2010: before then, it was called Algebraic Topological Methods in Computer Science, and since then it has been Algebraic Topology: Methods, Computation and Science.

Previous conferences in the series are:

1. 2001 ATMCS 2001, Stanford, CA, USA
2. 2004 ATMCS 2004, London, Ontario, Canada
3. 2008 ATMCS 2008, Paris, France
4. 2010 ATMCS 2010, Münster, Germany

Furthermore there have been workshops organized under the heading Geometric and Topological Methods in Concurrency (and Distributed Systems) in Aalborg, Denmark (1999 and 2001), Penn State, PA, USA (2000), Toulouse, France (2002), Marseille, France (2003), Amsterdam, the Netherlands (2004), San Francisco, CA, USA (2005), Bonn, Germany (2006) and Aalborg, Denmark (2010).

Applied and computational topology refers to the adaptation of topological ideas and techniques to study problems in science and engineering.  The further development of topological techniques for use in applications and the creation of new areas of application in the subject are amongst the goals of this workshop.  The workshop will bring together leading researchers in this emerging discipline as well as providing an opportunity for young mathematicians to get involved in it.

Arrangements

***PLEASE NOTE THAT THIS WORKSHOP IS NOW CLOSED FOR APPLICATIONS*

Venue and Presentation Facilities
The workshop will be held at 15 South College Street, Edinburgh.  You may also find this map useful for the workshop. 

All main lectures (allocated one hour in the Programme) will be held in the Newhaven Lecture Theatre.  The lecture theatre is fitted with data projection, visualiser (the new generation of over-head) and a smart-board.  In addition, two blackboards have been installed.  The projector and one board may be used simultaneously.  

Contributed Talks (allocated 30 minutes in the Programme) will take place in parallel sessions - some in the Newhaven Lecture Theatre and some in the Cramond Room (a seminar room on Level 2 of the ICMS building).   The Cramond Room will have a data projector, overhead projector, and blackboards. 

 

Registration Fee
The registration fee is now payable:

• 50.00 GBP for all invited speakers;

• 100.00 GBP for all contributed talk speakers and all other participants.

This can be paid in advance by completing the details on this credit/debit card payment form.   As email is not secure, please print the form and return it by fax using the fax number at the top of the form.  ICMS will take your payment and a receipt will be given to you at Registration.  Alternatively, we can accept sterling cheques, made payable to Heriot-Watt University but sent to Audrey Brown, ICMS, 15 South College Street, Edinburgh, EH8 9AA.  If you have any difficulty in paying in advance please email Audrey Brown (audrey.brown@icms.org.uk).   It is possible for you to pay on arrival at Registration at ICMS. 

 

Accommodation

• Invited Speakers will have heard from ICMS about the accommodation booked on their behalf by ICMS.

• For all contributed speakers and other participants, ICMS cannot reserve accommodation for you. Suggestions for accommodation close to ICMS can be found here.

Wireless Access
The workshop venue, 15 South College Street, has wireless access throughout. On arrival at Registration you will be given instructions and a code for accessing the wireless network.  For those without laptops, there will also be a couple of computers available for you to check your emails.

Meals and Refreshments
Morning and afternoon refreshments will be provided on each day of the workshop. A buffet lunch will be provided at ICMS in the Chapterhouse on the ground floor of 15 South College Street on Monday and Wednesday. A workshop dinner will be held on Wednesday in the Playfair Library of Old College (opposite the workshop venue). The workshop grant will cover the cost of this catering. 

Travel
Information about travel to the UK and Edinburgh is available here. Lothian buses charge 1.40 GBP for a single journey and 3.50 GBP for a day ticket. Please note that the exact fare is required and no change is given.

A taxi directly from the airport will cost approximately 18.00 to 20.00 GBP to the city centre for a one-way journey.

From the airport, you can take the airport bus Airlink to the city centre. It will cost you 3.50 GBP for a single ticket, or 6.00 GBP return. More details on the airport bus Airlink is available here. The bus will take you to Waverley Bridge (next to Waverley Railway Station).

If travelling by train, please note that Edinburgh has two railway stations - Waverley Railway Station being the main station and closest to the workshop venue at ICMS and George Square. If you alight at Edinburgh Waverley, the workshop venue is an easy 10 minute walk over North and South Bridge map. The second railway station is called Haymarket and is at the West End of the city centre.

Please note that it is your responsibility to have adequate travel insurance to cover medical and other emergencies that may occur on your trip.

 

Mathematical Art
During the workshop The Atrium on Level 3 of the ICMS building will house an exhibition of mathematical art, showcasing work by Radmila Sazdanovic, Mikael Vejdemo-Johansson and Madeleine Shepherd & Julia Collins.  This exhibition will be open to workshop delegates for the duration of the meeting and also open to the public on the afternoon of Tuesday 3 July only. A few more details are available on the exhibition page.

Poster pdf file to download.

 

Public Lecture by Robert Ghrist
On the evening of Tuesday 3rd July there will be a Public Lecture by Robert Ghrist (University of Pennsylvania) entitled "The Mathematics of Holes".    This lecture will be held in Lecture Theatre 183, Old College, South Bridge, Edinburgh - the building directly opposite ICMS.  Doors will open at 5.30pm, last entry at 6pm.   Lecture: 18.00-19.00.  A SEAT HAS BEEN RESERVED FOR ALL WORKSHOP PARTICIPANTS - YOU DO NOT NEED TO BOOK A TICKET.   

Abstract: Mathematics implicates motions and machines; computations and colourings; the strings and arrows of life. Perhaps the grandest expression of the beauty and power of mathematics is revealed in the quantification and qualification that which is not there: holes. Topology - the mathematics of holes - will be surveyed with a fresh look at the many ways in which topology is used in data management, networks, and optimization.

Poster pdf file to download.

 

Tourist attractions and events
If you are arriving in the days prior to the workshop or staying after the event, you may be interested in some of these Scottish tourist events or attractions. 

 

Visas
ICMS asks attendees to check if they require a visa for entry to the United Kingdom. This government website gives more information. If you do require a visa ICMS can provide you with a letter which may assist with your application.  

 

Programme

Please note that this Programme may be subject to change.

Important note about abstracts: It has been reported that the links to the abstracts in the presentations section below do not work in Safari or Google Chrome browsers. If you are using one of these browsers you can view the abstracts using this pdf file.

Monday 2 July

08.15 - 08.45	Registration and coffee
08.45 - 09.00	Introductions and welcome
09.00 - 10.00	Shmuel Weinberger (University of Chicago) Disordered solids and the dynamics of bounded geometry   pdf of presentation
10.00 - 11.00	Sayan Mukherjee (Duke University) Probability measures on the space of persistence diagrams  pdf of presentation
11.00 - 11.30	Coffee/Tea in the Chapterhouse, Level 1
11.30 - 12.30	Stephen Smale (City University of Hong Kong) Topology and immunology
12.30 - 14.00	Lunch provided in the Chapterhouse, Level 1
	Parallel Sessions - Newhaven Lecture Theatre, Level 4
14.00 - 14.30	Matthew Arnold (University of Bristol) Statistical aspects of persistent homology  pdf of presentation
14.35 - 15.05	Giseon Heo (University of Alberta) Topological analysis of variance with applications in landmark data set pdf of presentation
15.10 - 15.40	Yasuaki Hiraoka (Kyushu University) Applications of persistent diagrams to protein compressibility and phylogenetic trees
15.45 - 16.15	Coffee/Tea in the Chapterhouse
16.15 - 16.45	Daniel Müllner (Stanford University) Consistent scale selection for exploratory visualization and analysis of data sets
16.50 - 17.20	Monica Nicolau (Stanford University) Unraveling the biology of disease through data transformations and topological data analysis
	Parallel Sessions - Cramond Room, Level 2
14.00 - 14.30	Marek Krcal (Charles University) Computing all maps into a sphere  pdf of presentation
14.35 - 15.05	Carl McTague (University of Southampton) A new approach to Euler calculus for continuous integrands   pdf of presentation
15.10 - 15.40	Facundo Mémoli (University of Adelaide) Metric geometry and persistent topology
15.45 - 16.15	Coffee/Tea in the Chapterhouse
16.15 - 16.45	Ulrich Bauer (Institute of Science and Technology Austria) Topological simplification problems  pdf of presentation
16.50 - 17.20	Michal Adamaszek (University of Warwick) Homology and complexity  pdf of presentation
17.30 - 19.30	Wine reception in the Chapterhouse, Level 1

 

Tuesday 3 July

09.00 - 10.00	Jean-Daniel Boissonnat (INRIA, Sophia Antipolis) Delaunay-type structures for manifolds   pdf of presentations
10.00 - 11.00	Rien van de Weijgaert (Groningen University) The geometry and topology of the cosmic web
11.00 - 11.30	Coffee/Tea in the Chapterhouse
11.30 - 12.30	Frederic Chazal (INRIA Saclay - Île-de-France) Detection and approximation of linear structures in metric spaces  pdf of presentations
12.30	Free afternoon
13.30 - 17.30	Mathematical Art Exhibition opens to the public (in the Atrium, Level 3, ICMS)
17.30 - 19.00	Public Lecture by Robert Ghrist (University of Pennsylvania) The Mathematics of Holes Venue: Lecture Theatre 183, Old College, South Bridge. Doors open 17.30, for lecture 18.00-19.00

 

Wednesday 4 July

09.00 - 10.00	Michael Atiyah (University of Edinburgh) Analysis, combinatorics and computation   pdf of presentation
10.00 - 11.00	Nati Linial (Hebrew University of Jerusalem) Graphs as "model organisms" for topologists
11.00 - 11.30	Coffee/Tea in the Chapterhouse
11.30 - 12.30	Matthew Kahle (Ohio State University) The topological signature of randomness
12.30 - 14.00	Lunch provided in the Chapterhouse
14.00 - 15.00	Leonidas Guibas (Stanford University) Understanding shapes through mappings
15.10 - 15.40	Coffee/Tea in the Chapterhouse
	Parallel Sessions - Newhaven Lecture Theatre, Level 4
15.45 - 16.15	Jesus Gonzalez (Center for Research and Advanced Studies) Immersion dimension and topological complexity of projective product spaces pdf of presentation
16.15 - 16.45	Yuli Rudyak (University of Florida) On higher topological complexity and configuration spaces
16.50 - 17.20	Dirk Schuetz (Durham University) Homology of moduli spaces of linkages in high-dimensional euclidean space pdf of presentation
	Parallel Sessions - Cramond Room, Level 2
15.45 - 16.15	Francesco Vaccarino (Politecnico di Torino - ISI Foundation) Minimal resolutions of graded modules and multi bar codes
16.15 - 16.45	Claudia Landi (Università di Modena e Reggio Emilia) Uniqueness of models in persistent homology   pdf of presentation
16.50 - 17.20	Tomasz Kaczynski (Université de Sherbrooke) Suspension of a measuring function   pdf of presentation
19.00	Workshop Dinner at Playfair Library, Old College, South Bridge, Edinburgh

 

Thursday 5 July

09.00 - 10.00	Andrzej Szymczak (Colorado School of Mines) Piecewise constant vector field topology  pdf of presentation
10.00 - 11.00	Daniel Cohen (Louisiana State University) Topological complexity of hyperplane complements
11.00 - 11.30	Coffee/Tea in the Chapterhouse
11.30 - 12.30	Eric Goubault (CEA LIST, Saclay) Recent advances in directed algebraic topology, with applications to concurrent and distributed systems    pdf of presentation
12.30 - 14.00	Lunch break
14.00 - 15.00	Sanjeevi Krishnan (University of Pennsylvania) Poincaré duality and linear optimization
15.10 - 15.40	Coffee/Tea in the Chapterhouse
	Parallel Sessions - Newhaven Lecture Theatre, Level 4
15.45 - 16.15	Dai Tamaki (Shinshu University) A Salvetti-type model for configuration spaces
16.15 - 16.45	Lisbeth Fajstrup (Aalborg University) Periodicity and the trace space algorithm
	Parallel Sessions - Cramond Room, Level 2
15.45 - 16.15	Hubert Wagner (Jagiellonian University/IST Austria) Computational topology in text mining   pdf of presentation
16.15 - 16.45	Pawel Dlotko (Jagiellonian University) Computational (co)homology – applications and recent progress in computations pdf of presentation

 

Friday 6 July

09.00 - 10.00	Herbert Edelsbrunner (Institute of Science and Technology Austria) Adaptive triangulation of a digital image   pdf of presentation
10.00 - 11.00	Primoz Skraba (Jozef Stefan Institute) and Mikael Vejdemo-Johansson (University of St Andrews) Persistence modules — algebra and algorithms    pdf of presentation
11.00 - 11.30	Coffee/Tea in the Chapterhouse
11.30 - 12.30	Vin de Silva (Pomona College) Persistent cohomology and circle-valued functions
12.30 - 14.00	Lunch break
14.00 - 15.00	Marian Mrozek (Jagiellonian University) Homological persistence of maps
15.10 - 15.40	Coffee/Tea in the Chapterhouse
	Parallel Sessions - Newhaven Lecture Theatre, Level 4
15.45 - 16.15	Miroslav Kramar (Rutgers University) The dynamics of granular materials
16.15 - 16.45	Donald Sheehy (INRIA Saclay - Île-de-France) Linear-size approximations to the Vietoris-Rips filtration   pdf of presentation
16.50 - 17.20	Peter Franek (Czech Technical University in Prague) Topological degree computation based on interval arithmetic  pdf of presentation
	Parallel Sessions - Cramond Room, Level 2
15.45 - 16.15	David Balduzzi (Max Planck Institute for Intelligent Systems) An information-theoretic presheaf for distributed learning   pdf of presentation
16.15 - 16.45	Justin Curry (University of Pennsylvania) Cosheaves and dualities in generalized sensor networks  pdf of presentation
16.50 - 17.20	SangEon Han (Chonbuk National University) A new type of locally finite topological space and its applications   pdf of presentation

 

Presentations:

Presentation Details
Adamaszek, Michal
Homology and complexity
View Abstract Hide Abstract
We look for the boundary between easy (polynomial) and difficult (NP-hard) instances of computational problems for simplicial complexes. We take a combinatorial approach and exhibit a class of clique complexes of a natural class of graphs such that deciding their contractibility is polynomial but deciding triviality of any specified homology group is NP-hard. As a consequence we also prove that computing homology of arbitrary simplicial complexes given as a list of facets is NP-hard. (Joint work with Juraj Stacho).
Arnold, Matthew
Statistical aspects of persistent homology
View Abstract Hide Abstract
We are studying statistical aspects of persistent homology, within the framework of "Topological Data Analysis". For points sampled uniformly at random from a topological object in Euclidean space, the persistence barcodes contain some intervals that represent topological "features" and some intervals that represent "noise" which occurs as a result of our uniform sampling strategy. We investigate the null distribution of noisy intervals for uniform samples, by investigating the distribution of the full barcode for a uniform sample from the unit square. This directs us towards algorithmically identifying noisy intervals in a given barcode, so that the remaining intervals are classified as actual features of the underlying space. Related to this is the study of how the noisy intervals change when the sampled points are not uniformly sampled from the object. By using a kernel density estimate of the sample we can correct for the non-uniformity to return barcodes that behave similarly to those we would expect if we could have sampled uniformly. This allows us to identify the noisy intervals using the null distribution described earlier. Some results in both of these areas will be presented.
Atiyah, Sir Michael
Analysis, combinatorics and computation
View Abstract Hide Abstract
Many topological invariants of manifolds arise from analysis. Sometimes these can be computed combinatorially. The classical case is that of a compact Riemann surface where the genus g (the dimension of the space of holomorphic forms), or rather 2g-2, can be computed by Euler’s formula or by the Gauss integral. In higher dimensions things are much more complicated and there are subtleties on how good a combinatorial approximation has to be in order to compute a given invariant. I will pose some challenges in this direction.
Balduzzi, David
An information-theoretic presheaf for distributed learning
View Abstract Hide Abstract
Statistical learning theory bounds the expected error of a learning algorithm (on unseen data) based on the number of errors on a finite training set and the complexity of the algorithm, quantified by measures such as VC (Vapnik-Chervonenkis) entropy. Recently, attention has shifted from individual learning algorithms to distributed systems of learners such as deep belief networks, where theoretical guarantees are notably lacking. In my talk, I will formalize learning as performing an abstract measurement. VC entropy turns out to quantify the information generated by the measurement. The focus of the talk is then on the information-theoretic structure of distributed measurements, which is captured by the quale: a family of sections of a suitably defined presheaf. Using the quale I geometrically represent (i) the information content of a measurement; (ii) the extent to which a measurement is context-dependent; and (iii) whether a measurement decomposes into independent submeasurements. Finally, I show that only indecomposable measurements are more informative than the sum of their submeasurements -- which has implications for the VC-entropy of distributed systems and, therefore, bounds on their expected error.
Bauer, Ulrich
Topological simplification problems
View Abstract Hide Abstract
We show that function simplification on surfaces is easy: given a function f on a surface and a tolerance d>0, we construct a function g subject to |g-f|<=d such that g has a minimum number of critical points. Our construction relies on a connection between discrete Morse theory and persistent homology. The simplified function g achieves the lower bound dictated by the stability theorem of persistent homology. The solution can be computed in linear time after persistence pairs have been computed. (Joint work with Carsten Lange and Max Wardetzky) On the other hand, we show that isosurface simplification is hard: given a function f on a subset of R^3 and a tolerance d > 0, it is NP-hard to find a function g subject to |g-f|<=d such that the t-level set {x: g(x)=t} minimizes the total Betti number. The proof uses a reduction from the homological factorization problem: given a pair of spaces L c K, is there a space L c X c K such that the induced homomorphisms of L c X and X c K are surjective and injective, respectively? This problem is shown to be NP-complete even for simplicial pairs embeddable in R^3. (Joint work with Nina Amenta, Dominique Attali, Olivier Devillers, Marc Glisse, and André Lieutier)
Boissonnat, Jean-Daniel
Delaunay-type structures for manifolds
View Abstract Hide Abstract
The Delaunay triangulation is one of the most popular geometric data structure. In the last decade, the restricted Delaunay triangulation emerged as a central concept in surface meshing and reconstruction. It however suffers from several limitations when considering more general manifolds. We will discuss some recent variations on this concept and present new Delaunay-type simplicial complexes and practical algorithms to triangulate smooth submanifolds.
Chazal, Frederic
Detection and approximation of linear structures in metric spaces
View Abstract Hide Abstract
In many real-world applications data come as discrete metric spaces sampled around 1-dimensional linear structures (metric trees or graphs). Building on elementary tools of the theory of delta-hyperbolic spaces introduced by M Gromov in 1987, we provide a framework in which one can measure how much a given data set can be approximated by 1-dimensional metric structures and we provide algorithms to reconstruct such approximating structures. We will also illustrate the performances of our algorithm on various data sets. This is a joint work with Jian Sun (Mathematical Sciences Center, Tsinghua University).
Cohen, Daniel
Topological complexity of hyperplane complements
View Abstract Hide Abstract
The topological complexity of a space is a homotopy type invariant motivated by the motion planning problem from robotics. We determine this invariant for the complement of an arbitrary arrangement of complex hyperplanes.
Curry, Justin
Cosheaves and dualities in generalized sensor networks
View Abstract Hide Abstract
In this talk, I will introduce the computational framework of cellular sheaves and cosheaves, and advocate for a different perspective on Morse Theory, persistent homology, network coding and pursuit-evasion problems in sensor networks. This framework provides local-to-global results as well as generalizations of Poincaré duality. To provide concrete examples, I will introduce a new model for sensing with different modalities (colours, sounds, etc.) and show how a long exact sequence of sheaf cohomology provides forcing results that allow you to infer what you don't know from what you do.
de Silva, Vin
Persistent cohomology and circle-valued functions
View Abstract Hide Abstract
I will discuss the use of persistent cohomology to discover meaningful circle-valued coordinates on a data set, in the spirit of nonlinear dimensionality reduction (NLDR) algorithms such as Isomap, LLE, and Laplacian Eigenmaps. The construction is closely related to the Abel-Jacobi map in algebraic geometry. There are possible applications to the study and simulation of dynamical systems. My collaborators in this work (some of it completed, some of it in progress) include Morozov, Vejdemo-Johansson, Skraba, Mischaikow.
Dlotko, Pawel
Computational (co)homology – applications and recent progress in computations
View Abstract Hide Abstract
Computational homology and cohomology have recently become important tools in solving many problems in science and engineering. Consequently, new, efficient algorithms are needed to handle the amounts of data coming from real world problems. In this talk some recent developments and algorithms will be presented. I will concentrate on new methods to partially parallelize, distribute and speed up (co)homology and persistent (co)homology computations. Moreover a quick survey of recent applications of presented theory and algorithms will be given.
Edelsbrunner, Herbert
Adaptive triangulation of a digital image
View Abstract Hide Abstract
To enjoy a digital version of the Jordan Curve Theorem, it is common to use the closed topology for the foreground and the open topology for the background of a 2-dimensional binary image. We introduce a single topology that enjoys this theorem for all thresholds decomposing a real-valued image into fore- and background. The topology is easy to construct and it generalizes to n-dimensional images. (Joint work with Olga Symonova.)
Fajstrup, Lisbeth
Periodicity and the trace space algorithm
View Abstract Hide Abstract
The executions of a parallel program is the space of directed paths or traces in a particular d-space. The topological invariants of the trace spaces are invariants of the program. For a non-looped, non-branching program, it is known how to generate a simplicial model of the trace space from a certain index category. For looped processes, the state space is a (directed)torus and the trace space is a disjoint union of trace spaces of deloopings. The index category for the trace space of the deloopings is developed from the once delooped case. When just one process is looped, the index category is generated as words in a regular language. The automaton is constructed.
Franek, Peter
Topological degree computation based on interval arithmetic
View Abstract Hide Abstract
I present a new algorithm for computing the topological degree deg(f,B,0) of a continuous (not necessary differentiable) function f:B->R^n defined on an n-dimensional box B. The algorithm separates numerical from combinatorial computation: the numerical part computes the subdivision of $partial B$ to a set of (n-1)-dimensional boxes such that on each box F, there exist a component $f_{j(F)}$ with constant sign $s(F)$ on F. This subdivision can be calculated by the use of interval arithmetic. The information ${F,j(F), s(F)}$ determines the degree uniquely and the combinatorial part calculates it recursively, using a some degree identities. I explain the main part of the algorithm, illustrate it on simple examples, give a proof of correctness, report on computational experiments and show applications in the verification of zeros of systems of equations. Comparison of the effectivity with older algorithm is discussed and an online demonstrations of the program implementation will be shown. (Joint work with Stefan Ratschan).
Gonzalez, Jesus
Immersion dimension and topological complexity of projective product spaces
View Abstract Hide Abstract
It is well known that Farber's topological complexity of real projective spaces agrees with the Euclidean immersion dimension of these manifolds. However this is an isolated phenomenon; even Davis' projective product spaces fail to have such a property. Indeed, for those manifolds, we characterize the immersion dimension and their topological complexity in terms of suitable generalizations of axial maps, from which the (large) differences between both invariants are apparent.
Goubault, Eric
Recent advances in directed algebraic topology, with applications to concurrent and distributed systems
View Abstract Hide Abstract
I will give a survey of some of the recent results in directed algebraic topology, with a view to practical computations of topological invariants (trace spaces, component categories etc.) and their use for proving properties on concurrent and distributed programs.
Guibas, Leonidas
Understanding shapes through mappings
View Abstract Hide Abstract
We discuss a number of ways of understanding shape collections jointly, through the mechanism of (1) finding novel representations and algorithms for maps between the shapes, and (2) investigating the resulting map networks so as to evaluate each map in the context of other maps.
Han, SangEon
A new type of locally finite topological space and its applications
View Abstract Hide Abstract
In the fields of pure and applied topology we have the question: Is there a topological structure which can be used for studying both continuous and digital spaces? As an answer, this talk suggests a new type of locally finite topological space (or space set topology). Since the structure can play an important role in classical, computer, discrete and digital geometry as well as digital topology, the paper proposes a Jordan curve theorem of a simple closed SST-curve. Finally, the paper shows that an SST can be used for studying both continuous and digital spaces so that it plays an important role in both classical and digital topology and further, discrete and computational geometry.
Heo, Giseon
Topological analysis of variance with applications in landmark data set
View Abstract Hide Abstract
It is common to reduce the dimensionality of data before applying classical multivariate analysis techniques in statistics. Persistent homology, a recent development in computational topology, has shown to be useful for analyzing high dimensional (non-linear) data. In this talk, we connect computational topology with the traditional analysis of variance and demonstrate this synergy on a three-dimensional orthodontic landmark data set derived from the maxillary complex. Combining appropriate techniques of both persistent homology and analysis of variance results in a better understanding of the data's non-linear features over and above what could have been achieved by classical means.
Hiraoka, Yasuaki
Applications of persistent diagrams to protein compressibility and phylogenetic trees
View Abstract Hide Abstract
In this talk, we will present our recent research applying persistent diagrams to protein analysis. The first subject is the compressibility of proteins. We will show that we can derive a topological quantity from persistent diagrams of proteins which has a good linear correlation to the experimental data of compressibility. Next subject is phylogenetic trees of proteins. Based on the distance function on persistent diagrams, we can define a tree for a given group of proteins. This tree possesses more information of three dimensional geometric/topological structures of proteins than a conventional phylogenetic trees derived by a one dimensional amino acid sequences. We show some examples which classify hereditary properties. We also discuss our trial to detect hereditarily important regions in a protein structure by persistent diagrams.
Kaczynski, Tomasz
Suspension of a measuring function
View Abstract Hide Abstract
Given a measuring function f on M with values in R, we construct a measuring function g on the based topological suspension of M, also with values in R, and with the property that its rank invariants are those of f with the homology dimension q shifted by one. In particular, the 0-dimensional rank invariant, equivalently, the size function of g is trivial, and its one dimensional rank invariant provides the same information as the size function of f. We use this as a simple model for generating examples aimed at testing various topological invariants of shape for efficiency. In particular, our construction gives some insight into a discussion on what is a better tool in shape comparison: the rank invariant studied for several homology dimensions or the multidimensional size function.
Kahle, Matthew
The topological signature of randomness
View Abstract Hide Abstract
We will survey the emerging field of probabilistic topology. This will include recent work which shows that almost all d-dimensional flag complexes have nontrivial homology (with real coefficients), only in degree [d/2].
Kramar, Miroslav
The dynamics of granular materials
View Abstract Hide Abstract
We present a novel approach based on topological measurements to study force chain structures of particulate systems. We concentrate on systems undergoing compression. Our method distinguishes different types of friction as well as different amounts of polydispersity. These topological measures can be also used to understand the dynamic features of the system and can be correlated to phenomena such as jamming.
Krcal, Marek
Computing all maps into a sphere
View Abstract Hide Abstract
We present an algorithm for computing [X,Y], i.e., all homotopy classes of continuous maps X -> Y, where X,Y are topological spaces given as finite simplicial complexes, Y is (d-1)-connected for some d>1 (for example, Y can be the d-dimensional sphere S^d), and dim X < 2d-1. These conditions on X,Y guarantee that [X,Y] has a natural structure of a finitely generated Abelian group, and the algorithm finds generators and relations for it. We combine several tools and ideas from homotopy theory (such as Postnikov systems, simplicial sets, and obstruction theory) with algorithmic tools from effective algebraic topology (spaces with effective homology). We hope that a further extension of the methods developed here will yield an algorithm for computing, in some cases of interest, the Z_2-index, which is a quantity playing a prominent role in Borsuk--Ulam style applications of topology in combinatorics and geometry, e.g., in topological lower bounds for the chromatic number of a graph. In a certain range of dimensions, deciding the embeddability of a simplicial complex into R^d also amounts to a {Z_2-index} computation. This is the main motivation of our work.
Krishnan, Sanjeevi
Poincaré duality and linear optimization
View Abstract Hide Abstract
In this talk, I will recast and generalize certain dualities in linear optimization, such as max-flow min-cut, as a form of twisted Poincaré Duality for spacetimes and more singular "directed spaces." Flows correspond to the top-dimensional homology, taking local coefficients and values in a sheaves of semigroups, on directed spaces. Cuts correspond to certain distinguished sections of a dualizing sheaf. Thus max-flow min-cut dualities extend to higher dimensional analogues of flows, higher dimensional analogues of directed graphs, and constraints more complicated than upper bounds. I will describe the formal result and some real-world applications.
Landi, Claudia
Uniqueness of models in persistent homology
View Abstract Hide Abstract
We consider the question whether the rank of persistent homology groups of a function f defined on a minifold M uniquely characterizes f, at least up to self-homeorphisms of the manifold. For a function f taking values in IR this is easily seen to be false. However, we can give partially positive answers to this question for vector-valued functions. Our uniqueness problem is clearly strictly related to the decision problem in shape matching, that is, given two patterns, deciding whether there exists a transformation taking one pattern to the other pattern. Rephrased differently, we wish to study to which extent persistent homology can give rise to complete shape invariants.
Linial, Nati
Graphs as "model organisms" for topologists
View Abstract Hide Abstract
There is an important lesson we can take from biologists. The study of genetics greatly relies on investigations of the fruit fly Drosophila melanogaster. Flies are clearly much simpler than humans, but the principles that underlie their genetics are very similar to ours. This simplicity helps us study their genetics and offers at the same time easier access to key ingredients of our own genetics. Similar example abound. Zebrafish are model organisms for development, the worm C. elegans for body plan etc. Now everyone knows that graphs are "just" one-dimensional simplicial complexes. Does this offer any help? In this talk I will try to claim that there is a huge potential in using what we already know in graph theory as a basis for future developments in geometry and topology. Graph theory has advanced tremendously in the last half century and many of the insights gained can be quite relevant and useful in more complicated (e.g., higher-dimensional) contexts. Among the concrete ideas I will try to highlight are the role of the probabilistic method, and the local theory of graphs.
McTague, Carl
A new approach to Euler calculus for continuous integrands
View Abstract Hide Abstract
I will describe a new approach to Euler calculus for continuous real-valued integrands inspired by the work of Baryshnikov-Ghrist. The resulting calculus is additive and satisfies a Fubini theorem under fairly general conditions.
Mémoli, Facundo
Metric geometry and persistent topology
View Abstract Hide Abstract
We study questions regarding the stability of persistence diagrams arising from pseudo-metric data. One first example is the stability of persistence diagrams of Vietoris-Rips filtrations. These can be proved to be stable in the Gromov- Hausdorff sense. Similar stability results hold for more general filtrations that arise from finite metric measure spaces, in which case the stability is w.r.t. the Gromov-Wasserstein metric. These stability results provide lower bounds for the GH distance, whose computation in general leads to NP-hard problems. These results have applications in data analysis and shape classification.
Mrozek, Marian
Homological persistence of maps
View Abstract Hide Abstract
When a topological space is known only from sampling, persistence provides a useful tool to study its homological properties. In many applications one can sample not only the space, but also a map acting on the space. The understanding of the topological features of the map is often of interest, in particular in time series analysis. We recall the concept of persistence in finite dimensional vector spaces and use it to study the persistence of eigenspaces of maps induced in homology. Our technique is based on the graph approach to computing homology of maps. (This is joint work with Herbert Edelsbrunner and Grzegorz Jablonski)
Mukherjee, Sayan
Probability measures on the space of persistence diagrams
View Abstract Hide Abstract
This paper shows that the space of persistence diagrams has properties that allow for the definition of probability measures which support expectations, variances, percentiles and conditional probabilities. This provides a theoretical basis for a statistical treatment of persistence diagrams, for example computing sample averages and sample variances of persistence diagrams. We first prove that the space of persistence diagrams with the Wasserstein metric is complete and separable. We then prove a simple criterion for compactness in this space. These facts allow us to show the existence of the standard statistical objects needed to extend the theory of topological persistence to a much larger set of applications. We also develop algorithms to compute Frechet means a provide law of large numbers results for these means.
Müllner, Daniel
Consistent scale selection for exploratory visualization and analysis of data sets
View Abstract Hide Abstract
Choosing an appropriate scale is a frequently encountered problem in data analysis, and paradigms in the field support both the choice of strategies to make smart, definite choices and the hierarchical or persistence approach of looking at all scales at once. In the core of the “Mapper” algorithm for visualization and analysis of point cloud data, a scale choice must be made multiple times for overlapping fragments of the data set. We present the concept of a scale graph, where scale choices in neighbouring regions are brought into conjunction to make consistent decisions at local scale, while retaining global flexibility. By selecting an optimal path through the scale graph, we can make more plausible choices, overcome existing weaknesses, validate results more easily and simplify the data analysis process for the user. (Joint work with Gunnar Carlsson, Facundo Mémoli and Gurjeet Singh.)
Nicolau, Monica
Unraveling the biology of disease through data transformations and topological data analysis
View Abstract Hide Abstract
The past decade has witnessed developments in the field of biology that have brought about profound changes in understanding the dynamic of disease and of biological systems in general. New technology has given biologists an unprecedented wealth of information, but it has generated data that is hard to analyze mathematically, thereby making its biological interpretation difficult. These challenges have given rise to a myriad novel exciting mathematical problems and have provided an impetus to modify and adapt traditional mathematics tools, as well as develop novel techniques to tackle the data analysis problems raised in biology. I will discuss a general approach to address some of these computational challenges by way of a combination of data transformations and topological methods, to highlight specific biologically driven questions. These methods have been applied in a wide range of settings, in particular for the study of the biology of disease. I will discuss some concrete applications to these methods, including their use to discover a new type of breast cancer and the associated biology that drives the disease, identify disease progression trends, and highlighting the driving mechanisms in acute myeloid leukemia. Much of this is joint work with Gunnar Carlsson.
Rudyak, Yuli
On higher topological complexity and configuration spaces
View Abstract Hide Abstract
In 2010 I developed the concept of Farber topological complexity, by introducing the so-called higher topological complexity. The symmetrization of this invariant leads to interesting geometry and, in particular, to research some cofiguration spaces. This is a joint work with Basabe, Gonzalez and Tamaki.
Schuetz, Dirk
Homology of moduli spaces of linkages in high-dimensional euclidean space
View Abstract Hide Abstract
We consider closed linkages in d-dimensional euclidean space, up to translations and rotations, and obtain topological information on the resulting moduli spaces and how they depend on the lengths of the links. In particular, we calculate the Poincare polynomial in the case d=5 in terms of the length vector determining the linkage.
Sheehy, Donald
Linear-size approximations to the Vietoris-Rips filtration
View Abstract Hide Abstract
The Vietoris-Rips filtration is a versatile tool in topological data analysis. Unfortunately, it is often too large to construct in full. We show how to construct an O(n)-size filtered simplicial complex on an n-point metric space such that the persistence diagram is a good approximation to that of the Vietoris-Rips filtration. The filtration can be constructed in O(n log n) time. The constants depend only on the doubling dimension of the metric space and the desired tightness of the approximation. For the first time, this makes it computationally tractable to approximate the persistence diagram of the Vietoris-Rips filtration across all scales for large data sets. Our approach uses a hierarchical net-tree to sparsify the filtration. We can either sparsify the data by throwing out points at larger scales to give a zigzag filtration, or sparsify the underlying graph by eliminating edges at larger scales to give a standard filtration. Both methods yield the same guarantees.
Skraba, Primoz
Persistence modules — algebra and algorithms (joint talk with Mikael Vejdemo-Johansson)
View Abstract Hide Abstract
Persistent homology was identified by Zomorodian-Carlsson (2005) as homology in the category of graded k[t]-modules, for an underlying field k. Recognizing this algebraic framework allows us to draw on lessons from computational algebra when working out algorithms in computational topology. We demonstrate some fundamental facts about the category of graded k[t]-modules, and some constructions from computational commutative algebra relevant to the computation of persistent homology: giving constructions for kernels, cokernels, images, pushouts, pullbacks, tensor products, and symmetric and external powers in the category of graded k[t]-modules. These allow, inter alia, for the purely algebraic computation of image, kernel and cokernel persistence, and suggest an out-of-order algorithm for computing persistent homology.
Smale, Stephen
Topology and immunology
View Abstract Hide Abstract
Topology of spaces of genes will be discussed.
Szymczak, Andrzej
Piecewise constant vector field topology
View Abstract Hide Abstract
The talk will focus on recent work on algorithms for computing Morse decompositions and approximating recurrent dynamics of piecewise constant vector fields, motivated by scientific visualization applications.
Tamaki, Dai
A Salvetti-type model for configuration spaces
View Abstract Hide Abstract
We propose a combinatorial/categorical model for configuration spaces of "good" cell complexes. The model is realized as the classifying space of a topological category by using the notion of cellular and stellar stratified spaces.
Vaccarino, Francesco
Minimal resolutions of graded modules and multi bar codes
View Abstract Hide Abstract
A polynomial ring over a filed is a PID. This is the main reason why persistent homology can be encoded by a simple bar code. To understand multi persistence one needs to deal with rings of higher projective dimension. However a polynomial ring in several variables is not the right choice. Instead one should look at the representation of the product of the poset of natural numbers. Homological properties of the category of its representations are much easier than for polynomial rings. The aim of this talk is to discuss those properties, in particular illustrate how easy it is to construct minimal resolutions in this category. These resolutions are the multi bar codes. This is a join work with W Chacholski and M Scolamiero.
van de Weijgaert, Rien
The geometry and topology of the cosmic web
View Abstract Hide Abstract
The Cosmic Web is the fundamental spatial organization of matter on scales of a few up to a hundred Megaparsec, scales at which the Universe still resides in a state of moderate dynamical evolution. Galaxies, intergalactic gas and dark matter exist in a wispy weblike spatial arrangement consisting of dense compact clusters, elongated filaments, and sheetlike walls, amidst large near-empty void regions. While the complex intricate structure of the cosmic web contains a wealth of cosmological information, its quantification has remained a major challenge. In this lecture, we describe recent work towards invoking concepts from computational topology and computational geometry to our understanding of the structure of the Cosmic Web and to new insights into the conditions in the primordial Universe out of which it emerged. Voronoi and Delaunay tessellations form the basis of DTFE, the formalism to infer the density field of an anisotropic and multiscale mass distribution sampled by discrete points. I will describe the new Nexus multiscale morphology filter, based on DTFE, that helps to identify the filaments and walls in the maps of the galaxy distribution. Also, I will shortly describe the Watershed Void Finder, the Morse theory based technique to outline voids in the galaxy distribution. An important aspect of our understanding of the Cosmic Web concerns the connectivity of the various components. This leads us to recent work on the topological analysis of the Megaparsec scale distribution. To this end, we resort to the homology of the weblike structure, and determine the scale-dependent Betti numbers. To infer this from the discrete spatial galaxy distribution (or of particles in computer models of cosmic structure formation) we extract the Betti numbers from alpha shapes. We have studied the alpha complex of the cosmic weblike point patterns, in order to assess the signature of filaments, walls and voids. Of considerable importance within the context of the multiscale nature of the cosmic mass distribution, is the information contained in persistence diagrams. Amongst others, I will describe recent work on persistence properties of Gaussian and non-Gaussian random density fields, which form the initial conditions out of which the cosmic web emerged through the force of gravity.
Vejdemo-Johansson, Mikael
Persistence modules — algebra and algorithms (joint talk with Primoz Skraba)
View Abstract Hide Abstract
Persistent homology was identified by Zomorodian-Carlsson (2005) as homology in the category of graded k[t]-modules, for an underlying field k. Recognizing this algebraic framework allows us to draw on lessons from computational algebra when working out algorithms in computational topology. We demonstrate some fundamental facts about the category of graded k[t]-modules, and some constructions from computational commutative algebra relevant to the computation of persistent homology: giving constructions for kernels, cokernels, images, pushouts, pullbacks, tensor products, and symmetric and external powers in the category of graded k[t]-modules. These allow, inter alia, for the purely algebraic computation of image, kernel and cokernel persistence, and suggest an out-of-order algorithm for computing persistent homology.
Wagner, Hubert
Computational topology in text mining
View Abstract Hide Abstract
I would like to present an application of computational topology, especially persistence, to analysis of text documents. More precisely: analysis of the structure of similarities within a corpus of text documents. First, some basic tools from the field of text-mining will be presented. With these tools we map text data into a high dimensional space, which can be treated with topological methods. Then, we give an interpretation to the information captured by persistence. Finally, we overview the computational difficulties and describe the technique of iterated Morse decomposition we use to preprocess the data. (The project is done in collaboration with Google, within the Google Research Award program.)
Weinberger, Shmuel
Disordered solids and the dynamics of bounded geometry
View Abstract Hide Abstract
I will explain a program of J Bellissard and S Ulgen-Yildirim associating a pre-foliated space to complete manifolds with bounded geometry with (anticipated) applications to quasicrystals and less ordered solids.

Participants

Name	Institution
Adamaszek, Michal	University of Warwick
Adams, Henry	Stanford University
Arnold, Matthew	University of Bristol
Atiyah, Sir Michael	University of Edinburgh
Attali, Dominique	CNRS
Bak, Anthony	Stanford University
Bak, Rune Harder	Rejselagat for matematikere
Balduzzi, David	Max Planck Institute for Intelligent Systems
Bauer, Ulrich	Institute of Science and Technology Austria
Belchi Guillamon, Francisco	University of Malaga
Boissonnat, Jean-Daniel	INRIA, Sophia Antipolis
Botnan, Magnus Bakke	Norwegian University of Science and Technology
Brodzki, Jacek	University of Southampton
Capitelli, Nicolas	University of Buenos Aires
Carlsson, Gunnar	Stanford University
Chazal, Frederic	INRIA Saclay - Île-de-France
Chernov, Alexey	Durham University
Cohen, Daniel	Louisiana State University
Costa, Armindo	University of Warwick
Curry, Justin	University of Pennsylvania
de Silva, Vin	Pomona College
Dlotko, Pawel	Jagiellonian University
Edelsbrunner, Herbert	Institute of Science and Technology Austria
Fajstrup, Lisbeth	Aalborg University
Farber, Michael	University of Warwick
Ferri, Massimo	University of Bologna
Fourman, Michael	University of Edinburgh
Franek, Peter	Czech Technical University in Prague
Gamble, Jennifer	North Carolina State University
Ghrist, Robert	University of Pennsylvania
Glisse, Marc	INRIA
Gonzalez, Jesus	Center for Research and Advanced Studies (CINVESTAV)
Goubault, Eric	CEA LIST, Saclay
Greenlees, John	University of Sheffield
Guibas, Leonidas	Stanford University
Gutiérrez, Bárbara	Center for Research and Advanced Studies (CINVESTAV)
Han, SangEon	Chonbuk National University
Henselman, Gregory	University of Pennsylvania
Heo, Giseon	University of Alberta
Hiraoka, Yasuaki	Kyushu University
Jardine, Rick	University of Western Ontario
Kaczynski, Tomasz	Université de Sherbrooke
Kahle, Matthew	Ohio State University
Kalisnik, Sara	Stanford University
Kramar, Miroslav	Rutgers University
Krcal, Marek	Charles University
Krishnan, Sanjeevi	University of Pennsylvania
Kurlin, Vitaliy	Durham University
Landi, Claudia	Università di Modena e Reggio Emilia
Linial, Nati	Hebrew University of Jerusalem
Lipsky, David	University of Pennsylvania
McTague, Carl	University of Southampton
Mémoli, Facundo	University of Adelaide
Mischaikow, Konstantin	Rutgers, State University of New Jersey
Mramor, Neža	University of Ljubljana
Mrozek, Marian	Jagiellonian University
Mukherjee, Sayan	Duke University
Müllner, Daniel	Stanford University
Nicolau, Monica	Stanford University
Oudot, Steve	INRIA Saclay - Île-de-France
Palmer, Chris	University of Edinburgh
Pausinger, Florian	Institute of Science and Technology Austria
Pavesic, Petar	University of Ljubljana
Ranicki, Andrew	University of Edinburgh
Raussen, Martin	Aalborg University
Rudyak, Yuli	University of Florida
Sazdanovic, Radmila	University of Pennsylvania
Schuetz, Dirk	Durham University
Sheehy, Donald	INRIA Saclay - Île-de-France
Skraba, Primoz	Jozef Stefan Institute
Smale, Stephen	City University of Hong Kong
Szymczak, Andrzej	Colorado School of Mines
Tamaki, Dai	Shinshu University
Teh, Nicholas	University of Oxford
Thatcher, Courtney	Bard College at Simon's Rock
Vaccarino, Francesco	Politecnico di Torino - ISI Foundation
van de Weijgaert, Rien	Groningen University
Vejdemo-Johansson, Mikael	University of St Andrews
Virk, Ziga	University of Ljubljana
Wagner, Hubert	Jagiellonian University/IST Austria
Wedrich, Paul	University of Cambridge
Weinberger, Shmuel	University of Chicago
Yao, Yuan	Peking University