Search Results

Documents authored by Maria, Clément

Document
DOI: 10.4230/LIPIcs.SoCG.2025.38
An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number

Authors: Colleen Delaney, Clément Maria, and Eric Samperton

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Quantum topology provides various frameworks for defining and computing invariants of manifolds inspired by quantum theory. 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 analyze the computational complexity of state sum invariants of 3-manifolds derived from Tambara-Yamagami categories. While these categories are the simplest source of state sum invariants beyond finite abelian groups (whose invariants can be computed in polynomial time) their computational complexities are yet to be fully understood. We first establish that the invariants arising from even the smallest Tambara-Yamagami categories are #P-hard to compute, so that one expects the same to be true of the whole family. Our main result is then the existence of a fixed parameter tractable algorithm to compute these 3-manifold invariants, where the parameter is the first Betti number of the 3-manifold with ℤ/2ℤ coefficients. 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 computable in polynomial time. Thus while one generally expects quantum invariants to be hard to compute classically, our results suggest that the hardness of computing state sum invariants from Tambara-Yamagami categories arises from classical 3-manifold topology rather than the quantum nature of the algebraic input.
Cite as

Colleen Delaney, Clément Maria, and Eric Samperton. An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{delaney_et_al:LIPIcs.SoCG.2025.38,
  author =	{Delaney, Colleen and Maria, Cl\'{e}ment and Samperton, Eric},
  title =	{{An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.38},
  URN =		{urn:nbn:de:0030-drops-231901},
  doi =		{10.4230/LIPIcs.SoCG.2025.38},
  annote =	{Keywords: 3-manifold, quantum invariant, fixed parameter tractable algorithm, topological parameter, Gauss sums, topological quantum field theory}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.78
Localized Geometric Moves to Compute Hyperbolic Structures on Triangulated 3-Manifolds

Authors: Clément Maria and Owen Rouillé

Published in: LIPIcs, Volume 244, 30th Annual 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 localized 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 as

Clément Maria and Owen Rouillé. Localized Geometric Moves to Compute Hyperbolic Structures on Triangulated 3-Manifolds. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 78:1-78:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.ESA.2022.78,
  author =	{Maria, Cl\'{e}ment and Rouill\'{e}, Owen},
  title =	{{Localized Geometric Moves to Compute Hyperbolic Structures on Triangulated 3-Manifolds}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{78:1--78:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.78},
  URN =		{urn:nbn:de:0030-drops-170168},
  doi =		{10.4230/LIPIcs.ESA.2022.78},
  annote =	{Keywords: knots and 3-manifolds, triangulation, hyperbolic structure, Thurston equations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.53
Parameterized Complexity of Quantum Knot Invariants

Authors: Clément Maria

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We give a general fixed parameter tractable algorithm to compute quantum invariants of links presented by planar 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)) ∈ N^O(√n) time algorithm to compute any Reshetikhin-Turaev invariant - derived from a simple Lie algebra 𝔤 - of a link presented by a planar diagram with n crossings and carving-width cw, and whose components are coloured with 𝔤-modules of dimension at most N. For example, this includes the N^{th}-coloured Jones polynomial.
Cite as

Clément Maria. Parameterized Complexity of Quantum Knot Invariants. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{maria:LIPIcs.SoCG.2021.53,
  author =	{Maria, Cl\'{e}ment},
  title =	{{Parameterized Complexity of Quantum Knot Invariants}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{53:1--53:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.53},
  URN =		{urn:nbn:de:0030-drops-138527},
  doi =		{10.4230/LIPIcs.SoCG.2021.53},
  annote =	{Keywords: computational knot theory, parameterized complexity, quantum invariants}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.56
Intrinsic Topological Transforms via the Distance Kernel Embedding

Authors: Clément Maria, Steve Oudot, and Elchanan Solomon

Published in: LIPIcs, Volume 164, 36th 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 (PHT) and Euler Characteristic Transform (ECT), both of which apply to shapes embedded in Euclidean space. The contribution of this paper is to define topological transforms for abstract metric measure spaces. Our proposed pipeline is to pre-compose the PHT or ECT with a Euclidean embedding derived from the eigenfunctions and eigenvalues of an integral operator. To that end, we define and study an integral operator called the distance kernel operator, and demonstrate that it gives rise to stable and quasi-injective topological transforms. We conclude with some numerical experiments, wherein we compute and compare the eigenfunctions and eigenvalues of our operator across a range of standard 2- and 3-manifolds.
Cite as

Clément Maria, Steve Oudot, and Elchanan Solomon. Intrinsic Topological Transforms via the Distance Kernel Embedding. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.SoCG.2020.56,
  author =	{Maria, Cl\'{e}ment and Oudot, Steve and Solomon, Elchanan},
  title =	{{Intrinsic Topological Transforms via the Distance Kernel Embedding}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{56:1--56:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.56},
  URN =		{urn:nbn:de:0030-drops-122145},
  doi =		{10.4230/LIPIcs.SoCG.2020.56},
  annote =	{Keywords: Topological Transforms, Persistent Homology, Inverse Problems, Spectral Geometry, Algebraic Topology, Topological Data Analysis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.64
Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants

Authors: Clément Maria and Jonathan Spreer

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

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 as

Clément Maria and Jonathan Spreer. Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{maria_et_al:LIPIcs.ESA.2016.64,
  author =	{Maria, Cl\'{e}ment and Spreer, Jonathan},
  title =	{{Admissible Colourings of 3-Manifold Triangulations for Turaev-Viro Type Invariants}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.64},
  URN =		{urn:nbn:de:0030-drops-64050},
  doi =		{10.4230/LIPIcs.ESA.2016.64},
  annote =	{Keywords: low-dimensional topology, triangulations of 3-manifolds, cohomology theory, Turaev-Viro invariants, combinatorial algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact