Title Hardness of computation of quantum invariants on 3-manifolds with restricted topology
Authors Henrique Ennes, Clément Maria
Preprint arXiv:2311.08514 (2023)

Abstract Quantum invariants in low dimensional topology offer a wide variety of valuable invariants of knots and 3-manifolds, presented by explicit formulas that are readily computable. Their computational complexity has been actively studied and is tightly connected to topological quantum computing. In this article, we prove that for any 3-manifold quantum invariant in the Reshetikhin-Turaev model, there is a deterministic polynomial time algorithm that, given as input an arbitrary closed 3-manifold M, outputs a closed 3-manifold M′ with same quantum invariant, such that M′ is hyperbolic, contains no low genus embedded incompressible surface, and is presented by a strongly irreducible Heegaard diagram. Our construction relies on properties of Heegaard splittings and the Hempel distance. At the level of computational complexity, this proves that the hardness of computing a given quantum invariant of 3-manifolds is preserved even when severely restricting the topology and the combinatorics of the input. This positively answers a question raised by Samperton.

arXiv: 2503.02814

Title An algorithm for Tambara-Yamagami quantum invariants of 3-manifolds, parameterized by the first Betti number
Authors Colleen Delaney, Clément Maria, Eric Samperton
Conference International Symposium on Computational Geometry (SoCG 2025)

Abstract Quantum topology provides various frameworks for defining and computing invariants of manifolds. One such framework of substantial interest in both mathematics and physics is the Turaev-Viro-Barrett-Westbury state sum construction, which uses the data of a spherical fusion category to define topological invariants of triangulated 3-manifolds via tensor network contractions. In this work we consider a restricted class of state sum invariants of 3-manifolds derived from Tambara-Yamagami categories. These categories are particularly simple, being entirely specified by three pieces of data: a finite abelian group, a bicharacter of that group, and a sign +/-1. Despite being one of the simplest sources of state sum invariants, the computational complexities of Tambara-Yamagami invariants are yet to be fully understood. We make substantial progress on this problem. Our main result is the existence of a general fixed parameter tractable algorithm for all such topological invariants, where the parameter is the first Betti number of the 3-manifold with ℤ/2ℤ coefficients. We also explain that these invariants are sometimes #P-hard to compute (and we expect that this is almost always the case). Contrary to other domains of computational topology, such as graphs on surfaces, very few hard problems in 3-manifold topology are known to admit FPT algorithms with a topological parameter. However, such algorithms are of particular interest as their complexity depends only polynomially on the combinatorial representation of the input, regardless of size or combinatorial width. Additionally, in the case of Betti numbers, the parameter itself is easily computable in polynomial time.

arXiv: 2311.08514

Title           Computing complete hyperbolic structures on cusped 3-manifolds
Authors     Clément Maria, Owen Rouillé
Conference European Symposium on Algorithms (ESA 2022)

Abstract A fundamental way to study 3-manifolds is through the geometric lens, one of the most prominent geometries being the hyperbolic one. We focus on the computation of a complete hyperbolic structure on a connected orientable hyperbolic 3-manifold with torus boundaries. This family of 3-manifolds includes the knot complements. This computation of a hyperbolic structure requires the resolution of gluing equations on a triangulation of the space, but not all triangulations admit a solution to the equations. In this paper, we propose a new method to find a triangulation that admits a solution to the gluing equations, using convex optimization and combinatorial modifications. It is based on Casson and Rivin s reformulation of the equations. We provide a novel approach to modify a triangulation and update its geometry, along with experimental results to support the new method.

Cite BibTex on the DBLP         arXiv: 2112.06360

Title Hard diagrams of the unknot
Authors Benjamin A. Burton, Hsien-Chih Chang, Maarten Löffler, Arnaud de Mesmay, Clément Maria, Saul Schleimer, Eric Sedgwick, Jonathan Spreer
Journal Experimental Mathematics (to appear)

Abstract We present three "hard" diagrams of the unknot. They require (at least) three extra crossings before they can be simplified to the trivial unknot diagram via Reidemeister moves in S2. Both examples are constructed by applying previously proposed methods. The proof of their hardness uses significant computational resources. We also determine that no small "standard" example of a hard unknot diagram requires more than one extra crossing for Reidemeister moves in S2.

arXiv: 2104.14076

Title           Computation of large asymptotics of 3-manifold quantum invariants
Authors     Clément Maria, Owen Rouillé
Conference     SIAM Symposium on Algorithm Engineering and Experiments (ALENEX) 2021

Abstract Quantum topological invariants have played an important role in computational topology, and they are at the heart of major modern mathematical conjectures. In this article, we study the experimental problem of computing large r values of Turaev-Viro invariants TVr. We base our approach on an optimized backtracking algorithm, consisting of enumerating combinatorial data on a triangulation of a 3-manifold. We design an easily computable parameter to estimate the complexity of the enumeration space, based on lattice point counting in polytopes, and show experimentally its accuracy. We apply this parameter to a preprocessing strategy on the triangulation, and combine it with multi-precision arithmetic in order to compute the Turaev-Viro invariants. We finally study the improvements brought by these optimizations compared to state-of-the-art implementations, and verify experimentally Chen and Yang's volume conjecture on a census of closed 3-manifolds.

Cite BibTex on the DBLP         DOI: 10.1137/1.9781611976472.15         arXiv: 2010.14316

Title           Intrinsic topological transforms via the distance kernel embedding
Authors     Clément Maria, Steve Oudot, Elchanan Solomon
Conference     International Symposium on Computational Geometry (SoCG) 2020

Abstract Topological transforms are parametrized families of topological invariants, which, by analogy with transforms in signal processing, are much more discriminative than single measurements. The first two topological transforms to be defined were the Persistent Homology Transform and Euler Characteristic Transform, both of which apply to shapes embedded in Euclidean space. The contribution of this paper is to define topological transforms that depend only on the intrinsic geometry of a shape, and hence are invariant to the choice of embedding. To that end, given an abstract metric measure space, we define an integral operator whose eigenfunctions are used to compute sublevel set persistent homology. We demonstrate that this operator, which we call the distance kernel operator, enjoys desirable stability properties, and that its spectrum and eigenfunctions concisely encode the large-scale geometry of our metric measure space. We then define a number of topological transforms using the eigenfunctions of this operator, and observe that these transforms inherit many of the stability and injectivity properties of the distance kernel operator.

arXiv: 1912.02225 [Long version]         Bibtex & DOI 10.4230/LIPIcs.SoCG.2020.56 [Extended abstract]

Title           Parameterized complexity of quantum knot invariants
Authors     Clément Maria
Conference     International Symposium on Computational Geometry (SoCG) 2021

Abstract We give a general fixed parameter tractable algorithm to compute quantum invariants of links presented by diagrams, whose complexity is singly exponential in the carving-width (or the tree-width) of the diagram. In particular, we get a O(N^{3/2 cw} poly(n)) time algorithm to compute any Reshetikhin-Turaev invariant---derived from a simple Lie algebra g---of a link presented by a planar diagram with n crossings and carving-width cw, and whose components are coloured with g-modules of dimension at most N. For example, this includes the Nth coloured Jones polynomials and the Nth coloured HOMFLYPT polynomials.

arXiv: 1910.00477

Title           A Polynomial Time Algorithm to Compute Quantum Invariants of 3-manifolds with Bounded First Betti Number
Authors     Clément Maria, Jonathan Spreer
Journal     Foundation of Computational Mathematics (FoCM) (to appear 2019)
Conference     Symposium on Discrete Algorithms (SoDA) 2017: 2721-2732

Abstract In this article, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariants TV4,q, using the dimension of the first homology group of the manifold as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parameter. The computation of TV4,q is known to be #P-hard in general; using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the extremely large family of 3-manifolds with first homology group of bounded rank. Our algorithm is easy to implement and running times are comparable with running times to compute integral homology groups for standard libraries of triangulated 3- manifolds. The invariants we can compute this way are powerful: in combination with integral homology and using standard data sets we are able to roughly double the pairs of 3-manifolds we can distinguish. We hope this qualifies TV4,q to be added to the short list of standard properties (such as orientability, connectedness, Betti numbers, etc.) that can be computed ad-hoc when first investigating an unknown triangulation.

Cite BibTex on the DBLP         DOI: 10.1137/1.9781611974782.180         arXiv: 1607.02218

Title           Treewidth, crushing, and hyperbolic volume
Authors     Clément Maria, Jessica S. Purcell
Journal     Algebraic & Geometric Topology

Abstract We prove that there exists a universal constant c such that any closed hyperbolic 3-manifold admits a triangulation of treewidth at most c times its volume. The converse is not true: we show there exists a sequence of hyperbolic 3-manifolds of bounded treewidth but volume approaching infinity. Along the way, we prove that crushing a normal surface in a triangulation does not increase the carving-width, and hence crushing any number of normal surfaces in a triangulation affects treewidth by at most a constant multiple.

DOI: 10.2140/agt.2019.19.2625         arXiv: 1805.02357

Title           Discrete Morse Theory for Computing Zigzag Persistence
Authors     Clément Maria, Hannah Schreiber
Conference     WADS 2019: Algorithms and Data Structures

Abstract We introduce a theoretical and computational framework to use discrete Morse theory as an efficient preprocessing in order to compute zigzag persistent homology. From a zigzag filtration of complexes (Ki), we introduce a zigzag Morse filtration whose complexes (Ai) are Morse reductions of the original complexes (Ki), and we prove that they both have same persistent homology. This zigzag Morse filtration generalizes the filtered Morse complex of Mischaikow and Nanda, defined for standard persistence. The maps in the zigzag Morse filtration are forward and backward inclusions, as is standard in zigzag persistence, as well as a new type of map inducing non trivial changes in the boundary operator of the Morse complex. We study in details this last map, and design algorithms to compute the update both at the complex level and at the homology matrix level when computing zigzag persistence. We deduce an algorithm to compute the zigzag persistence of a filtration that depends mostly on the number of critical cells of the complexes, and show experimentally that it performs better in practice.

Cite BibTex on the DBLP         DOI: 10.1007/978-3-030-24766-9_39 [Extended abstract]         arXiv: 1807.05172 [Long version]

Title           Computing Persistent Homology with Various Coefficient Fields in a Single Pass
Authors     Jean-Daniel Boissonnat, Clément Maria
Journal     Journal of Applied and Computational Topology JACT 3(1-2): 59-84 (2019)
Conference     European Symposium on Algorithms (ESA) 2014: 185-196

Abstract This article introduces an algorithm to compute the persistent homology of a filtered complex with various coefficient fields in a single matrix reduction. The algorithm is output-sensitive in the total number of distinct persistent homological features in the diagrams for the different coefficient fields. This computation allows us to infer the prime divisors of the torsion coefficients of the integral homology groups of the topological space at any scale, hence furnishing a more informative description of topology than persistence in a single coefficient field. We provide theoretical complexity analysis as well as detailed experimental results. The code is part of the Gudhi library.

Cite BibTex on the DBLP         DOI: 10.1007/978-3-662-44777-2_16         arXiv: 2001.02960

Title           Algorithms and Complexity of Turaev-Viro Invariants
Authors     Benjamin A. Burton, Clément Maria, Jonathan Spreer
Journal     Journal of Applied and Computational Topology 2018
Conference     International Colloquium on Automata, Languages, and Programming (ICALP) 2015: 281-293

Abstract The Turaev–Viro invariants are a powerful family of topological invariants for distinguishing between different 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them require exponential time. The invariants are parameterized by an integer r≥3. We resolve the question of complexity for r=3 and r=4, giving simple proofs that the Turaev–Viro invariants for r=3 can be computed in polynomial time, but computing the invariant for r=4 is #P-hard. Moreover, we describe an algorithm for arbitrary r, which is fixed-parameter tractable with respect to the treewidth of the dual graph of the input triangulation. We show through concrete implementation and experimentation that this algorithm is practical—and indeed preferable—to the prior state of the art for real computation. The algorithm generalises to every triangulated 3-manifold invariant defined from tensor network contraction.

Cite BibTex on Springer.com         DOI: 10.1007/s41468-018-0016-2         arXiv: 1503.04099

Title           Admissible Colourings of 3-manifold Triangulations for Turaev-Viro Type Invariants
Authors     Clement Maria, Jonathan Spreer
Conference     European Symposium on Algorithms (ESA) 2016: 64:1-64:16

Abstract Turaev-Viro invariants are amongst the most powerful tools to distinguish 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them rely on the enumeration of an extremely large set of combinatorial data defined on the triangulation, regardless of the underlying topology of the manifold. In the article, we propose a finer study of these combinatorial data, called admissible colourings, in relation with the cohomology of the manifold. We prove that the set of admissible colourings to be considered is substantially smaller than previously known, by furnishing new upper bounds on its size that are aware of the topology of the manifold. Moreover, we deduce new topology-sensitive enumeration algorithms based on these bounds. The paper provides a theoretical analysis, as well as a detailed experimental study of the approach. We give strong experimental evidence on large manifold censuses that our upper bounds are tighter than the previously known ones, and that our algorithms outperform significantly state of the art implementations to compute Turaev-Viro invariants.

Cite BibTex on the DBLP         DOI: 10.4230/LIPIcs.ESA.2016.64         arXiv: 1512.04648

Title           The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology
Authors     Jean-Daniel Boissonnat, Tamal K. Dey, Clément Maria
Journal     Algorithmica 73(3): 607-619 (2015)
Conference     European Symposium on Algorithms (ESA) 2013: 695-706

Abstract Persistent homology with coefficients in a field 𝔽 coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.

Cite BibTex on the DBLP         DOI: 10.1007/s00453-015-9999-4         arXiv: 1304.6813

Title           The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes
Authors     Jean-Daniel Boissonnat, Clément Maria
Journal     Algorithmica 70(3): 406-427 (2014)
Conference     European Symposium on Algorithms (ESA) 2012: 731-742

Abstract This paper introduces a new data structure, called simplex tree, to represent abstract simplicial complexes of any dimension. All faces of the simplicial complex are explicitly stored in a trie whose nodes are in bijection with the faces of the complex. This data structure allows to efficiently implement a large range of basic operations on simplicial complexes. We provide theoretical complexity analysis as well as detailed experimental results. We more specifically study Rips and witness complexes.

Cite BibTex on the DBLP         DOI: 10.1007/s00453-014-9887-3         arXiv: 2001.02581

Title           Zigzag Persistence via Reflections and Transpositions
Authors     Clément Maria, Steve Y. Oudot
Conference     Symposium on Discrete Algorithms (SoDA) 2015: 181-199

Abstract 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.

Cite BibTex on the DBLP         DOI: 10.1137/1.9781611973730.14

Title           The Gudhi Library: Simplicial Complexes and Persistent Homology
Authors     Clément Maria, Jean-Daniel Boissonnat, Marc Glisse, Mariette Yvinec
Conference     International Congress on Mathematical Software (ICMS) 2014: 167-174

Abstract We present the main algorithmic and design choices that have been made to represent complexes and compute persistent homology in the Gudhi library. The Gudhi library (Geometric Understanding in Higher Dimensions) is a generic C++ library for computational topology. Its goal is to provide robust, efficient, flexible and easy to use implementations of state-of-the-art algorithms and data structures for computational topology. We present the different components of the software, their interaction and the user interface. We justify the algorithmic and design decisions made in Gudhi and provide benchmarks for the code. The software, which has been developped by the first author, will be available soon at project.inria.fr/gudhi/software/.

Cite BibTex on the DBLP         DOI: 10.1007/978-3-662-44199-2_28

Title           An Exponential Lower Bound on the Complexity of Regularization Paths
Authors     Bernd Gärtner, Martin Jaggi, Clément Maria
Journal     Journal of Computational Geometry (JoCG) 3(1): 168-195 (2012)

Abstract For a variety of regularized optimization problems in machine learning, algorithms computing the entire solution path have been developed recently. Most of these methods are quadratic programs that are parameterized by a single parameter, as for example the Support Vector Machine (SVM). Solution path algorithms do not only compute the solution for one particular value of the regularization parameter but the entire path of solutions, making the selection of an optimal parameter much easier. It has been assumed that these piecewise linear solution paths have only linear complexity, i.e. linearly many bends. We prove that for the support vector machine this complexity can be exponential in the number of training points in the worst case. More strongly, we construct a single instance of n input points in d dimensions for an SVM such that at least Θ(2^n/2) = Θ(2^d) many distinct subsets of support vectors occur as the regularization parameter changes.

Cite BibTex on the DBLP         DOI: 10.20382/jocg.v3i1a9         arXiv: 0903.4817

Title           Computing Zigzag Persistent Cohomology
Authors     Clement Maria, Steve Oudot
Preprint     arXiv:1608.06039 2016

Abstract Zigzag persistent homology is a powerful generalisation of persistent homology that allows one not only to compute persistence diagrams with less noise and using less memory, but also to use persistence in new fields of application. However, due to the increase in complexity of the algebraic treatment of the theory, most algorithmic results in the field have remained of theoretical nature. This article describes an efficient algorithm to compute zigzag persistence, emphasising on its practical interest. The algorithm is a zigzag persistent cohomology algorithm, based on the dualisation of reflections and transpositions transformations within the zigzag sequence. We provide an extensive experimental study of the algorithm. We study the algorithm along two directions. First, we compare its performance with zigzag persistent homology algorithm and show the interest of cohomology in zigzag persistence. Second, we illustrate the interest of zigzag persistence in topological data analysis by comparing it to state of the art methods in the field, specifically optimised algorithm for standard persistent homology and sparse filtrations. We compare the memory and time complexities of the different algorithms, as well as the quality of the output persistence diagrams.

Cite BibTex on the DBLP         arXiv: 1608.06039

Title           Classification of Normal Curves on a Tetrahedron
Authors     Clément Maria, Jonathan Spreer
Conference     Young Researchers Forum at the Symposium on Computational Geometry 2016

Abstract In this article, we give a combinatorial classification of all normal curves drawn on the boundary of a tetrahedron. We characterise normal curves in terms of intersection numbers with the edges of the tetrahedron.

Title           Diamonds are a Quiver's Best Friend
Authors     Clément Maria
Conference     Young Researchers Forum at the Symposium on Computational Geometry 2015

Abstract Motivated by the theory of persistent homology and its algorithmic aspects, new theorems, called diamond principles, have been recently introduced to track the changes in the algebraic decomposition of a quiver rep- resentation under local transformations. We present in this article a new proof of Gabriel’s theorem for An-type quivers using these principles. The proof uses an elementary recursive argument and leads to an efficient algorithm for decomposing quiver representations.

Title           Normal Surfaces and Polynomial Computation of Quantum Invariants of 3-Manifolds
Authors     Clément Maria, Jonathan Spreer
Poster     XIX School on Differential Geometry, IMPA 2016

Title           Algorithmes et Structures de Données en Topologie Algorithmique
Authors     Clément Maria
Journal     1024 - Bulletin de la société informatique de France

Description Popularisation article I wrote after receiving the Gilles Kahn PhD award in 2015.

Co-authors

Journal Articles, Conference Proceedings and Preprints (short list)

Journal Articles, Conference Proceedings and Preprints (chronological)

Peer-reviewed, other

Popularisation of science