BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Francis Sergeraert appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
A paper has recently been published in SIAM-JC. This paper is faulty: 1) The standard requirements about the definition of an algorithm are not respected, 2) The main point in the complexity study, namely the functional programming component, is absent. The Editorial Board of the SIAM JC had been warned a confirmed publication would be openly commented, it is the role of this text.
Given topological spaces X and Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X -> Y . We consider a computational version, where X, Y are given as finite simplicial complexes, and the goal is to compute [X,Y], i.e., all homotopy classes of such maps. We solve this problem in the stable range, where for some d >= 2, we have dim X <= 2d - 2 and Y is (d - 1)-connected; in particular, Y can be the d-dimensional sphere S^d. The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [X,Y] is known to be uncomputable for general X,Y, since for X = S^1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y. In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem, where we are given a subspace A of X and a map A -> Y and ask whether it extends to a map X -> Y, or computing the Z_2-index---everything in the stable range. Outside the stable range, the extension problem is undecidable.
By general case we mean methods able to process simplicial sets and chain complexes not of finite type. A filtration of the object to be studied is the heart of both subjects persistent homology and spectral sequences. In this paper we present the complete relation between them, both from theoretical and computational points of view. One of the main contributions of this paper is the observation that a slight modification of our previous programs computing spectral sequences is enough to compute also persistent homology. By inheritance from our spectral sequence programs, we obtain for free persistent homology programs applicable to spaces not of finite type (provided they are spaces with effective homology) and with Z-coefficients (significantly generalizing the usual presentation of persistent homology over a field). As an illustration, we compute some persistent homology groups (and the corresponding integer barcodes) in the case of a Postnikov tower.
In this paper, three Computational Topology methods (namely effective homology, persistent homology and discrete vector fields) are mixed together to produce algorithms for homological digital image processing. The algorithms have been implemented as extensions of the Kenzo system and have shown a good performance when applied on some actual images extracted from a public dataset.
This text was written and used for a MAP Summer School at the University of Genova, August 28 to September 2, 2006. Available since then on the web site of the second author, it has been used and referenced by several colleagues working in Commutative Algebra and Algebraic Topology. To make safer such references, it was suggested to place it on the Arxiv repository. It is a relatively detailed exposition of the use of the Basic Perturbation Lemma to make constructive Homological Algebra (standard Homological Algebra is not constructive) and how this technology can be used in Commutative Algebra (Koszul complexes) and Algebraic Topology (effective versions of spectral sequences).
In an earlier paper of Cadek, Vokrinek, Wagner, and the present authors, we investigated an algorithmic problem in computational algebraic topology, namely, the computation of all possible homotopy classes of maps between two topological spaces, under suitable restriction on the spaces. We aim at showing that, if the dimensions of the considered spaces are bounded by a constant, then the computations can be done in polynomial time. In this paper we make a significant technical step towards this goal: we show that the Eilenberg-MacLane space K(Z,1), represented as a simplicial group, can be equipped with polynomial-time homology (this is a polynomial-time version of effective homology considered in previous works of the third author and co-workers). To this end, we construct a suitable discrete vector field, in the sense of Forman's discrete Morse theory, on K(Z,1). The construction is purely combinatorial and it can be understood as a certain procedure for reducing finite sequences of integers, without any reference to topology.The Eilenberg-MacLane spaces are the basic building blocks in a Postnikov system, which is a "layered" representation of a topological space suitable for homotopy-theoretic computations. Employing the result of this paper together with some other results on polynomial-time homology, in another paper we obtain, for every fixed k, a polynomial-time algorithm for computing the k-th homotopy group pi_k(X) of a given simply connected space X, as well as the first k stages of a Postnikov system for X, and also a polynomial-time version of the algorithm of Cadek et al. mentioned above.