Fixed-parameter tractable computation of Reshetikhin--Turaev knot polynomials via tensor networks
Pith reviewed 2026-06-30 04:33 UTC · model grok-4.3
The pith
Reshetikhin-Turaev knot polynomials are computable in fixed-parameter tractable time with respect to a parameter linear in the tree-width of any input knot diagram.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The computation of Reshetikhin-Turaev knot polynomials via tensor contractions on the associated tensor networks is fixed-parameter tractable with respect to a parameter at most linear in the tree-width of the input knot diagram. When combined with existing approximation algorithms for tree decomposition, this recovers the sub-exponential bound e^{O(sqrt(n))} for the time complexity of computing any Reshetikhin-Turaev knot polynomial.
What carries the argument
Tensor network whose contraction computes the Reshetikhin-Turaev invariant, constructed so its treewidth is bounded linearly by the treewidth of the knot diagram.
If this is right
- The runtime is bounded by a function of the tree-width parameter alone.
- Any Reshetikhin-Turaev polynomial admits a sub-exponential algorithm running in e^{O(sqrt(n))}.
- The method applies uniformly once an R-matrix and ribbon element are supplied.
- An explicit implementation in SnapPy computes the polynomials from the given algebraic data.
Where Pith is reading between the lines
- Knots whose diagrams admit small tree-width become exactly computable at larger crossing numbers than brute-force methods allow.
- The same network-construction technique may apply to other diagrammatic invariants that reduce to tensor contractions.
- Improved practical tree-decomposition heuristics would directly tighten the observed running times without changing the asymptotic claim.
Load-bearing premise
A tensor network computing the invariant can be constructed from any knot diagram with treewidth at most linear in the diagram's treewidth.
What would settle it
A sequence of knot diagrams in which every tensor network realizing the Reshetikhin-Turaev invariant has treewidth growing superlinearly with the diagram treewidth.
Figures
read the original abstract
We give a thorough analysis of the time complexity of computing Reshetikhin--Turaev knot polynomials via tensor contractions on the associated tensor networks, showing that the computation is fixed-parameter tractable with respect to a parameter at most linear in the tree-width of the input knot diagram. When combined with existing approximation algorithms for tree decomposition, this recovers the sub-exponential bound $e^{O(\sqrt{n})}$ for the time complexity of computing any Reshetikhin--Turaev knot polynomial. We accompany this paper with an implementation of such an algorithm in SnapPy, which computes any Reshetikhin--Turaev knot polynomial given its $R$-matrix and ribbon element.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims to provide a thorough analysis showing that Reshetikhin-Turaev knot polynomials can be computed via tensor contractions on networks derived from knot diagrams, establishing fixed-parameter tractability with respect to a parameter at most linear in the tree-width of the input diagram. Combined with existing approximation algorithms for tree decompositions, this is said to recover the sub-exponential time bound e^{O(√ n)}. The paper includes an accompanying implementation in SnapPy that takes an arbitrary R-matrix and ribbon element as input.
Significance. A correct FPT result for RT invariants parameterized by diagram treewidth would connect quantum topology with parameterized algorithms in a novel way and could be useful for low-treewidth diagrams. The provided SnapPy implementation is a strength for reproducibility. However, the central FPT claim appears to be a misclassification of an XP bound, which substantially reduces the significance of the complexity analysis.
major comments (2)
- [Abstract] Abstract: The assertion that the computation is fixed-parameter tractable (FPT) w.r.t. a parameter p = O(tw(D)) is incorrect. Tensor-network contraction for an RT invariant with R-matrix of dimension d runs in time d^{O(tw)} n^{O(1)}. Because the input includes the R-matrix (whose size is θ(d^4) or larger), this is |I|^{O(tw)} n^{O(1)} where |I| denotes total input size; such a bound is slicewise polynomial (XP) but not FPT, as no f(p) independent of d can absorb the d^{O(p)} factor.
- [Abstract] Abstract: The claimed recovery of the sub-exponential bound e^{O(√ n)} likewise contains no d factor. This is consistent with treating the representation dimension d as a fixed constant rather than part of the input, contradicting the statement that the algorithm takes an arbitrary R-matrix.
Simulated Author's Rebuttal
We thank the referee for their careful review and for identifying a key distinction between FPT and XP complexity classes in our analysis. We address the two major comments point by point below. We agree that revisions are required to correct the classification of the running time and to resolve the inconsistency regarding the dependence on the representation dimension d.
read point-by-point responses
-
Referee: [Abstract] Abstract: The assertion that the computation is fixed-parameter tractable (FPT) w.r.t. a parameter p = O(tw(D)) is incorrect. Tensor-network contraction for an RT invariant with R-matrix of dimension d runs in time d^{O(tw)} n^{O(1)}. Because the input includes the R-matrix (whose size is θ(d^4) or larger), this is |I|^{O(tw)} n^{O(1)} where |I| denotes total input size; such a bound is slicewise polynomial (XP) but not FPT, as no f(p) independent of d can absorb the d^{O(p)} factor.
Authors: We agree with the referee's analysis. When the R-matrix is provided as input (as the manuscript states), the running time d^{O(tw(D))} n^{O(1)} is XP rather than FPT, because the exponential factor depends on both the parameter tw(D) and the input size component d. We will revise the abstract, introduction, and complexity statements to correctly describe the result as slicewise polynomial (XP) parameterized by treewidth. The algorithmic approach and SnapPy implementation remain unchanged. revision: yes
-
Referee: [Abstract] Abstract: The claimed recovery of the sub-exponential bound e^{O(√ n)} likewise contains no d factor. This is consistent with treating the representation dimension d as a fixed constant rather than part of the input, contradicting the statement that the algorithm takes an arbitrary R-matrix.
Authors: We acknowledge the inconsistency. The stated bound e^{O(√ n)} implicitly treats d as constant, which conflicts with the claim of arbitrary R-matrix input. In the revised manuscript we will clarify that the sub-exponential bound holds when d is fixed (as is common for specific Reshetikhin–Turaev invariants), while the general case yields d^{O(√ n)} n^{O(1)}. We will update the abstract and relevant sections to remove the contradiction and state the dependence on d explicitly. revision: yes
Circularity Check
No circularity; derivation relies on standard tensor contraction bounds
full rationale
The paper's derivation chain consists of (1) constructing a tensor network from a knot diagram whose treewidth is O(tw(D)) and (2) invoking the known dynamic-programming contraction algorithm whose runtime is d^{O(tw)} n^{O(1)}. Neither step is self-definitional, nor does any fitted parameter get relabeled as a prediction. No self-citations are load-bearing for the complexity claim, and the R-matrix is explicitly supplied as input rather than derived from the result. The analysis is therefore self-contained against external algorithmic benchmarks; the FPT/XP distinction raised by the skeptic is a correctness issue, not a circularity reduction.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Tensor-network contraction complexity is governed by the treewidth of the underlying graph.
- standard math Approximation algorithms exist that produce tree decompositions of width O(sqrt n) in sub-exponential time.
Reference graph
Works this paper leans on
-
[1]
Turaev, V. G. , TITLE =. Invent. Math. , FJOURNAL =. 1988 , NUMBER =. doi:10.1007/BF01393746 , URL =
-
[2]
Kirillov, A. N. and Reshetikhin, N. Yu. , TITLE =. Infinite-dimensional. 1989 , ISBN =
1989
-
[3]
Amir, Eyal , TITLE =. Algorithmica , FJOURNAL =. 2010 , NUMBER =. doi:10.1007/s00453-008-9180-4 , URL =
-
[4]
Nature Reviews Physics , author =
Tensor networks for complex quantum systems , volume =. Nature Reviews Physics , author =. 2019 , pages =. doi:10.1038/s42254-019-0086-7 , abstract =
-
[5]
Bienstock, Dan , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1990 , NUMBER =. doi:10.1016/0095-8956(90)90066-9 , URL =
-
[6]
Korach, Ephraim and Solel, Nir , TITLE =. Discrete Appl. Math. , FJOURNAL =. 1993 , NUMBER =. doi:10.1016/0166-218X(93)90171-J , URL =
-
[7]
1999 , PAGES =
von zur Gathen, Joachim and Gerhard, J\"urgen , TITLE =. 1999 , PAGES =
1999
-
[8]
Korhonen, Tuukka , TITLE =. 2021. [2022] 2022 , ISBN =. doi:10.1109/FOCS52979.2021.00026 , URL =
-
[9]
Maria, Cl\'ement , TITLE =. 37th. 2021 , ISBN =
2021
-
[10]
Bar-Natan, Dror , TITLE =. Geom. Topol. , FJOURNAL =. 2005 , PAGES =. doi:10.2140/gt.2005.9.1443 , URL =
-
[11]
2002 , PAGES =
Ohtsuki, Tomotada , TITLE =. 2002 , PAGES =
2002
-
[12]
Freyd, P. and Yetter, D. and Hoste, J. and Lickorish, W. B. R. and Millett, K. and Ocneanu, A. , TITLE =. Bull. Amer. Math. Soc. (N.S.) , FJOURNAL =. 1985 , NUMBER =. doi:10.1090/S0273-0979-1985-15361-3 , URL =
-
[13]
and Tarjan, Robert Endre , TITLE =
Lipton, Richard J. and Tarjan, Robert Endre , TITLE =. SIAM J. Appl. Math. , FJOURNAL =. 1979 , NUMBER =. doi:10.1137/0136016 , URL =
-
[14]
Jackson, David M. and Moffatt, Iain , TITLE =. 2019 , PAGES =. doi:10.1007/978-3-030-05213-3 , URL =
-
[15]
Cygan, Marek and Fomin, Fedor V. and Kowalik, ukasz and Lokshtanov, Daniel and Marx, D\'aniel and Pilipczuk, Marcin and Pilipczuk, Micha. Parameterized algorithms , PUBLISHER =. 2015 , PAGES =. doi:10.1007/978-3-319-21275-3 , URL =
-
[16]
Markov, Igor L. and Shi, Yaoyun , TITLE =. SIAM J. Comput. , FJOURNAL =. 2008 , NUMBER =. doi:10.1137/050644756 , URL =
-
[17]
Meichanetzidis, Konstantinos and Kourtis, Stefanos , TITLE =. Phys. Rev. E , FJOURNAL =. 2019 , NUMBER =. doi:10.1103/physreve.100.033303 , URL =
-
[18]
J.A. Makowsky , keywords =. Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width , journal =. 2005 , note =. doi:https://doi.org/10.1016/j.dam.2004.01.016 , url =
-
[19]
, TITLE =
Burton, Benjamin A. , TITLE =. 34th. 2018 , ISBN =
2018
-
[20]
2025 , eprint=
On some log-concavity properties of the Alexander-Conway and Links-Gould invariants , author=. 2025 , eprint=
2025
-
[21]
Shumakovitch, Alexander N. , TITLE =. J. Knot Theory Ramifications , FJOURNAL =. 2011 , NUMBER =. doi:10.1142/S0218216511008802 , URL =
-
[22]
Alexander, J. W. , TITLE =. Trans. Amer. Math. Soc. , FJOURNAL =. 1928 , NUMBER =. doi:10.2307/1989123 , URL =
-
[23]
Jaeger, F. and Vertigan, D. L. and Welsh, D. J. A. , TITLE =. Math. Proc. Cambridge Philos. Soc. , FJOURNAL =. 1990 , NUMBER =. doi:10.1017/S0305004100068936 , URL =
-
[24]
Braid group, knot theory and statistical mechanics , SERIES =
Witten, Edward , TITLE =. Braid group, knot theory and statistical mechanics , SERIES =. 1989 , ISBN =. doi:10.1142/9789812798350\_0009 , URL =
-
[25]
Thistlethwaite, Morwen B. , TITLE =. Algebr. Geom. Topol. , FJOURNAL =. 2025 , NUMBER =. doi:10.2140/agt.2025.25.329 , URL =
-
[26]
2025 , eprint=
A Fast, Strong, Topologically Meaningful and Fun Knot Invariant , author=. 2025 , eprint=
2025
-
[27]
Bar-Natan, Dror and van der Veen, Roland , TITLE =. Proc. Amer. Math. Soc. , FJOURNAL =. 2019 , NUMBER =. doi:10.1090/proc/14166 , URL =
-
[28]
Stavros Garoufalidis and Shana Yunsheng Li , journal =. Patterns of the. 2026 , note =. doi:10.1080/10586458.2026.2651081 , eprint=
-
[29]
Stavros Garoufalidis and Shana Yunsheng Li and Josephine Yu , title =
-
[30]
Bar-Natan, Dror and van der Veen, Roland , TITLE =
-
[31]
Bar-Natan, Dror and van der Veen, Roland , TITLE =. Quantum Topol. , FJOURNAL =. 2024 , NUMBER =. doi:10.4171/qt/206 , URL =
-
[32]
KnotAtlas , HOWPUBLISHED =
-
[33]
Bridgeman, Jacob and Chubb, Christopher , TITLE =. J. Phys. A , FJOURNAL =. 2017 , NUMBER =. doi:10.1088/1751-8121/aa6dc3 , URL =
-
[34]
Burton, Benjamin , TITLE =. 36th. 2020 , MRCLASS =
2020
-
[35]
Culler, Marc and Dunfield, Nathan and Goerner, Matthias and Weeks, Jeffrey , TITLE =
-
[36]
GitHub repository , howpublished =
Shana Yunsheng Li , title =. GitHub repository , howpublished =. 2026 , publisher =
2026
-
[37]
Dunfield, Nathan and Friedl, Stefan and Jackson, Nicholas , TITLE =. Exp. Math. , FJOURNAL =. 2012 , NUMBER =. doi:10.1080/10586458.2012.669268 , URL =
-
[38]
New York J
Dunfield, Nathan and Garoufalidis, Stavros and Shumakovitch, Alexander and Thistlethwaite, Morwen , TITLE =. New York J. Math. , FJOURNAL =. 2010 , PAGES =
2010
-
[39]
Gabai, David , TITLE =. Mem. Amer. Math. Soc. , FJOURNAL =. 1986 , NUMBER =. doi:10.1090/memo/0339 , URL =
-
[40]
Garoufalidis, Stavros , TITLE =. Algebr. Geom. Topol. , FJOURNAL =. 2004 , PAGES =. doi:10.2140/agt.2004.4.935 , URL =
-
[41]
Garoufalidis, Stavros and Kashaev, Rinat , TITLE =. Publ. Res. Inst. Math. Sci. , FJOURNAL =. 2026 , NUMBER =. doi:10.4171/prims/62-1-3 , URL =
-
[42]
Garoufalidis, Stavros and Kashaev, Rinat and Kohli, Ben-Michael and Song, Jiebo and Tahar, Guillaume , TITLE =
-
[43]
Garoufalidis, Stavros and Matthew Harper and Kashaev, Rinat and Kohli, Ben-Michael and Wagner, Emmanuel , TITLE =
-
[44]
Garoufaldis, Stavros and Harper, Matthew and Kohli, Ben-Michael and Song, Jiebo and Tahar, Guillaume , TITLE =
-
[45]
Garoufalidis, Stavros and Li, Shana , TITLE =. 2024 , VERSION =. doi:10.7910/DVN/XE4TOF , HOWPUBLISHED =
-
[46]
Hedden, Matthew and Watson, Liam , TITLE =. Selecta Math. (N.S.) , FJOURNAL =. 2018 , NUMBER =. doi:10.1007/s00029-017-0351-5 , URL =
-
[47]
Hoste, Jim and Thistlethwaite, Morwen and Weeks, Jeff , TITLE =. Math. Intelligencer , FJOURNAL =. 1998 , NUMBER =. doi:10.1007/BF03025227 , URL =
-
[48]
Jablan, Slavik , TITLE =
-
[49]
Jones, Vaughan , TITLE =. Ann. of Math. (2) , FJOURNAL =. 1987 , NUMBER =
1987
-
[50]
Representation theory, mathematical physics, and integrable systems , SERIES =
Kashaev, Rinat , TITLE =. Representation theory, mathematical physics, and integrable systems , SERIES =. [2021] 2021 , MRCLASS =. doi:10.1007/978-3-030-78148-4\_15 , URL =
-
[51]
Kotelskiy, Artem and Watson, Liam and Zibrowius, Claudius , TITLE =
-
[52]
Kohli, Ben-Michael and Tahar, Guillaume , TITLE =
-
[53]
Osaka Math
Kinoshita, Shin'ichi and Terasaka, Hidetaka , TITLE =. Osaka Math. J. , FJOURNAL =. 1957 , PAGES =
1957
-
[54]
Lam, Chi-Chung and Sadayappan, P. and Wenger, Rephael , TITLE =. Parallel Process. Lett. , FJOURNAL =. 1997 , NUMBER =. doi:10.1142/S0129626497000176 , URL =
-
[55]
Links, Jon and Gould, Mark , TITLE =. Lett. Math. Phys. , FJOURNAL =. 1992 , NUMBER =. doi:10.1007/BF00420752 , URL =
-
[56]
Manolescu, Ciprian and Ozsv\'. On the. Proceedings of. 2008 , MRCLASS =
2008
-
[57]
Morton, Hugh , TITLE =. Math. Proc. Cambridge Philos. Soc. , FJOURNAL =. 1986 , NUMBER =. doi:10.1017/S0305004100063982 , URL =
-
[58]
Scott Morrison and Noah Snyder and Dylan Thurston , TITLE =
-
[59]
Murasugi, Kunio , TITLE =. J. Math. Soc. Japan , FJOURNAL =. 1958 , PAGES =. doi:10.2969/jmsj/01010094 , URL =
-
[60]
Neumann, Daniel Lopez and van der Veen, Roland , TITLE =
-
[61]
Ozsv\'. Odd. Algebr. Geom. Topol. , FJOURNAL =. 2013 , NUMBER =. doi:10.2140/agt.2013.13.1465 , URL =
-
[62]
An introduction to
Ozsv\'. An introduction to. Floer homology, gauge theory, and low-dimensional topology , SERIES =. 2006 , MRCLASS =
2006
-
[63]
Ozsv\'. On the. Adv. Math. , FJOURNAL =. 2005 , NUMBER =. doi:10.1016/j.aim.2004.05.008 , URL =
-
[64]
Ozsv\'. Knot. Topology Appl. , FJOURNAL =. 2004 , NUMBER =. doi:10.1016/j.topol.2003.09.009 , URL =
-
[65]
Faster identification of optimal contraction sequences for tensor networks , volume =
Pfeifer, Robert and Haegeman, Jutho and Verstraete, Frank , address =. Faster identification of optimal contraction sequences for tensor networks , volume =. Physical Review E , keywords =
-
[66]
Reshetikhin, Nikolai and Turaev, Vladimir , TITLE =. Comm. Math. Phys. , FJOURNAL =. 1990 , NUMBER =
1990
-
[67]
1994 , PAGES =
Turaev, Vladimir , TITLE =. 1994 , PAGES =
1994
-
[68]
Stoimenow, Alexander , TITLE =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.