Algorithms and complexity for Turaev-Viro invariants

Burton, Benjamin A., Maria, Clément and Spreer, Jonathan (2015). Algorithms and complexity for Turaev-Viro invariants. In: Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi and Bettina Speckmann, Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part 1. International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, (281-293). 6-10 June 2015. doi:10.1007/978-3-662-47672-7_23


Author Burton, Benjamin A.
Maria, Clément
Spreer, Jonathan
Title of paper Algorithms and complexity for Turaev-Viro invariants
Conference name International Colloquium on Automata, Languages, and Programming
Conference location Kyoto, Japan
Conference dates 6-10 June 2015
Proceedings title Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part 1   Check publisher's open access policy
Journal name Lecture Notes in Computer Science   Check publisher's open access policy
Place of Publication Heidelberg, Germany
Publisher Springer
Publication Year 2015
Year available 2015
Sub-type Fully published paper
DOI 10.1007/978-3-662-47672-7_23
Open Access Status Not Open Access
ISBN 9783662476710
9783662476727
ISSN 0302-9743
1611-3349
Editor Magnús M. Halldórsson
Kazuo Iwama
Naoki Kobayashi
Bettina Speckmann
Volume 9134
Start page 281
End page 293
Total pages 13
Chapter number 34
Total chapters 100
Collection year 2016
Language eng
Formatted Abstract/Summary
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 parameterised by an integer r≥3. We resolve the question of complexity for r=3 and r=4, giving simple proofs that computing Turaev-Viro invariants for r=3 is polynomial time, but for r=4 is #P-hard. Moreover, we give an explicit fixed-parameter tractable algorithm for arbitrary r, and show through concrete implementation and experimentation that this algorithm is practical—and indeed preferable—to the prior state of the art for real computation.
Keyword Computational topology
3-manifolds
Invariants
#P-hardness
Parameterised complexity
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Conference Paper
Collections: School of Mathematics and Physics
Official 2016 Collection
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 26 Aug 2015, 20:46:12 EST by Jonathan Spreer on behalf of Mathematics