pith. sign in

arxiv: 2606.29662 · v1 · pith:DIXEU7H4new · submitted 2026-06-29 · 🧮 math.GT

Fixed-parameter tractable computation of Reshetikhin--Turaev knot polynomials via tensor networks

Pith reviewed 2026-06-30 04:33 UTC · model grok-4.3

classification 🧮 math.GT
keywords Reshetikhin-Turaev invariantsknot polynomialstensor networksfixed-parameter tractabilitytreewidthknot diagramscomputational topology
0
0 comments X

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.

The paper analyzes computing Reshetikhin-Turaev knot polynomials by contracting tensor networks built from knot diagrams. It establishes that this process is fixed-parameter tractable when the parameter is bounded linearly by the tree-width of the diagram. Pairing the result with existing approximation algorithms for tree decompositions recovers a sub-exponential runtime of e to the O of square root n. The work includes a SnapPy implementation that accepts any R-matrix and ribbon element to produce the polynomial.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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

Figures reproduced from arXiv: 2606.29662 by Shana Yunsheng Li.

Figure 1
Figure 1. Figure 1: Running time for computing polynomials on various sets of knots. For the Vn-polynomial, k = 2 and d = 4n; for the n-colored Jones polynomial, k = 1 and d = n + 1 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An oriented long knot diagram of the 41 knot, with nonzero rota￾tion numbers labeled [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The tensor network resulted from an oriented long knot diagram of the 41 knot. free legs of the tensor network by, for example, setting at the beginning a0 = a10 = e1 in Example 2.5. 3. Bounding the time complexity 3.1. Contraction-width. We now restrict ourselves to tensor networks obtained by apply￾ing the Reshetikhin–Turaev functor to oriented long knot diagrams, where all legs of tensors have dimension… view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

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)
  1. [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.
  2. [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

2 responses · 0 unresolved

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

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

0 steps flagged

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

0 free parameters · 2 axioms · 0 invented entities

Review performed on abstract alone; no free parameters, ad-hoc axioms, or invented entities are described. The result rests on standard facts from parameterized complexity and tensor-network contraction that are treated as background.

axioms (2)
  • standard math Tensor-network contraction complexity is governed by the treewidth of the underlying graph.
    Invoked implicitly when the paper equates the FPT parameter to treewidth of the diagram.
  • standard math Approximation algorithms exist that produce tree decompositions of width O(sqrt n) in sub-exponential time.
    Used to recover the e^{O(sqrt n)} bound from the FPT result.

pith-pipeline@v0.9.1-grok · 5642 in / 1481 out tokens · 58876 ms · 2026-06-30T04:33:30.683070+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

68 extracted references · 38 canonical work pages

  1. [1]

    Turaev, V. G. , TITLE =. Invent. Math. , FJOURNAL =. 1988 , NUMBER =. doi:10.1007/BF01393746 , URL =

  2. [2]

    Kirillov, A. N. and Reshetikhin, N. Yu. , TITLE =. Infinite-dimensional. 1989 , ISBN =

  3. [3]

    Algorithmica , FJOURNAL =

    Amir, Eyal , TITLE =. Algorithmica , FJOURNAL =. 2010 , NUMBER =. doi:10.1007/s00453-008-9180-4 , URL =

  4. [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. [5]

    Bienstock, Dan , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1990 , NUMBER =. doi:10.1016/0095-8956(90)90066-9 , URL =

  6. [6]

    Discrete Appl

    Korach, Ephraim and Solel, Nir , TITLE =. Discrete Appl. Math. , FJOURNAL =. 1993 , NUMBER =. doi:10.1016/0166-218X(93)90171-J , URL =

  7. [7]

    1999 , PAGES =

    von zur Gathen, Joachim and Gerhard, J\"urgen , TITLE =. 1999 , PAGES =

  8. [8]

    Korhonen, Tuukka , TITLE =. 2021. [2022] 2022 , ISBN =. doi:10.1109/FOCS52979.2021.00026 , URL =

  9. [9]

    Maria, Cl\'ement , TITLE =. 37th. 2021 , ISBN =

  10. [10]

    Bar-Natan, Dror , TITLE =. Geom. Topol. , FJOURNAL =. 2005 , PAGES =. doi:10.2140/gt.2005.9.1443 , URL =

  11. [11]

    2002 , PAGES =

    Ohtsuki, Tomotada , TITLE =. 2002 , PAGES =

  12. [12]

    and Yetter, D

    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. [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. [14]

    and Moffatt, Iain , TITLE =

    Jackson, David M. and Moffatt, Iain , TITLE =. 2019 , PAGES =. doi:10.1007/978-3-030-05213-3 , URL =

  15. [15]

    and Kowalik, ukasz and Lokshtanov, Daniel and Marx, D\'aniel and Pilipczuk, Marcin and Pilipczuk, Micha

    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. [16]

    and Shi, Yaoyun , TITLE =

    Markov, Igor L. and Shi, Yaoyun , TITLE =. SIAM J. Comput. , FJOURNAL =. 2008 , NUMBER =. doi:10.1137/050644756 , URL =

  17. [17]

    Meichanetzidis, Konstantinos and Kourtis, Stefanos , TITLE =. Phys. Rev. E , FJOURNAL =. 2019 , NUMBER =. doi:10.1103/physreve.100.033303 , URL =

  18. [18]

    Makowsky , keywords =

    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. [19]

    , TITLE =

    Burton, Benjamin A. , TITLE =. 34th. 2018 , ISBN =

  20. [20]

    2025 , eprint=

    On some log-concavity properties of the Alexander-Conway and Links-Gould invariants , author=. 2025 , eprint=

  21. [21]

    , TITLE =

    Shumakovitch, Alexander N. , TITLE =. J. Knot Theory Ramifications , FJOURNAL =. 2011 , NUMBER =. doi:10.1142/S0218216511008802 , URL =

  22. [22]

    Alexander, J. W. , TITLE =. Trans. Amer. Math. Soc. , FJOURNAL =. 1928 , NUMBER =. doi:10.2307/1989123 , URL =

  23. [23]

    and Vertigan, D

    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. [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. [25]

    , TITLE =

    Thistlethwaite, Morwen B. , TITLE =. Algebr. Geom. Topol. , FJOURNAL =. 2025 , NUMBER =. doi:10.2140/agt.2025.25.329 , URL =

  26. [26]

    2025 , eprint=

    A Fast, Strong, Topologically Meaningful and Fun Knot Invariant , author=. 2025 , eprint=

  27. [27]

    Bar-Natan, Dror and van der Veen, Roland , TITLE =. Proc. Amer. Math. Soc. , FJOURNAL =. 2019 , NUMBER =. doi:10.1090/proc/14166 , URL =

  28. [28]

    Patterns of the

    Stavros Garoufalidis and Shana Yunsheng Li , journal =. Patterns of the. 2026 , note =. doi:10.1080/10586458.2026.2651081 , eprint=

  29. [29]

    Stavros Garoufalidis and Shana Yunsheng Li and Josephine Yu , title =

  30. [30]

    Bar-Natan, Dror and van der Veen, Roland , TITLE =

  31. [31]

    Quantum Topol

    Bar-Natan, Dror and van der Veen, Roland , TITLE =. Quantum Topol. , FJOURNAL =. 2024 , NUMBER =. doi:10.4171/qt/206 , URL =

  32. [32]

    KnotAtlas , HOWPUBLISHED =

  33. [33]

    Bridgeman, Jacob and Chubb, Christopher , TITLE =. J. Phys. A , FJOURNAL =. 2017 , NUMBER =. doi:10.1088/1751-8121/aa6dc3 , URL =

  34. [34]

    Burton, Benjamin , TITLE =. 36th. 2020 , MRCLASS =

  35. [35]

    Culler, Marc and Dunfield, Nathan and Goerner, Matthias and Weeks, Jeffrey , TITLE =

  36. [36]

    GitHub repository , howpublished =

    Shana Yunsheng Li , title =. GitHub repository , howpublished =. 2026 , publisher =

  37. [37]

    Dunfield, Nathan and Friedl, Stefan and Jackson, Nicholas , TITLE =. Exp. Math. , FJOURNAL =. 2012 , NUMBER =. doi:10.1080/10586458.2012.669268 , URL =

  38. [38]

    New York J

    Dunfield, Nathan and Garoufalidis, Stavros and Shumakovitch, Alexander and Thistlethwaite, Morwen , TITLE =. New York J. Math. , FJOURNAL =. 2010 , PAGES =

  39. [39]

    Gabai, David , TITLE =. Mem. Amer. Math. Soc. , FJOURNAL =. 1986 , NUMBER =. doi:10.1090/memo/0339 , URL =

  40. [40]

    Garoufalidis, Stavros , TITLE =. Algebr. Geom. Topol. , FJOURNAL =. 2004 , PAGES =. doi:10.2140/agt.2004.4.935 , URL =

  41. [41]

    Garoufalidis, Stavros and Kashaev, Rinat , TITLE =. Publ. Res. Inst. Math. Sci. , FJOURNAL =. 2026 , NUMBER =. doi:10.4171/prims/62-1-3 , URL =

  42. [42]

    Garoufalidis, Stavros and Kashaev, Rinat and Kohli, Ben-Michael and Song, Jiebo and Tahar, Guillaume , TITLE =

  43. [43]

    Garoufalidis, Stavros and Matthew Harper and Kashaev, Rinat and Kohli, Ben-Michael and Wagner, Emmanuel , TITLE =

  44. [44]

    Garoufaldis, Stavros and Harper, Matthew and Kohli, Ben-Michael and Song, Jiebo and Tahar, Guillaume , TITLE =

  45. [45]

    2024 , VERSION =

    Garoufalidis, Stavros and Li, Shana , TITLE =. 2024 , VERSION =. doi:10.7910/DVN/XE4TOF , HOWPUBLISHED =

  46. [46]

    Selecta Math

    Hedden, Matthew and Watson, Liam , TITLE =. Selecta Math. (N.S.) , FJOURNAL =. 2018 , NUMBER =. doi:10.1007/s00029-017-0351-5 , URL =

  47. [47]

    Hoste, Jim and Thistlethwaite, Morwen and Weeks, Jeff , TITLE =. Math. Intelligencer , FJOURNAL =. 1998 , NUMBER =. doi:10.1007/BF03025227 , URL =

  48. [48]

    Jablan, Slavik , TITLE =

  49. [49]

    Jones, Vaughan , TITLE =. Ann. of Math. (2) , FJOURNAL =. 1987 , NUMBER =

  50. [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. [51]

    Kotelskiy, Artem and Watson, Liam and Zibrowius, Claudius , TITLE =

  52. [52]

    Kohli, Ben-Michael and Tahar, Guillaume , TITLE =

  53. [53]

    Osaka Math

    Kinoshita, Shin'ichi and Terasaka, Hidetaka , TITLE =. Osaka Math. J. , FJOURNAL =. 1957 , PAGES =

  54. [54]

    and Wenger, Rephael , TITLE =

    Lam, Chi-Chung and Sadayappan, P. and Wenger, Rephael , TITLE =. Parallel Process. Lett. , FJOURNAL =. 1997 , NUMBER =. doi:10.1142/S0129626497000176 , URL =

  55. [55]

    Links, Jon and Gould, Mark , TITLE =. Lett. Math. Phys. , FJOURNAL =. 1992 , NUMBER =. doi:10.1007/BF00420752 , URL =

  56. [56]

    Manolescu, Ciprian and Ozsv\'. On the. Proceedings of. 2008 , MRCLASS =

  57. [57]

    Morton, Hugh , TITLE =. Math. Proc. Cambridge Philos. Soc. , FJOURNAL =. 1986 , NUMBER =. doi:10.1017/S0305004100063982 , URL =

  58. [58]

    Scott Morrison and Noah Snyder and Dylan Thurston , TITLE =

  59. [59]

    Murasugi, Kunio , TITLE =. J. Math. Soc. Japan , FJOURNAL =. 1958 , PAGES =. doi:10.2969/jmsj/01010094 , URL =

  60. [60]

    Neumann, Daniel Lopez and van der Veen, Roland , TITLE =

  61. [61]

    Ozsv\'. Odd. Algebr. Geom. Topol. , FJOURNAL =. 2013 , NUMBER =. doi:10.2140/agt.2013.13.1465 , URL =

  62. [62]

    An introduction to

    Ozsv\'. An introduction to. Floer homology, gauge theory, and low-dimensional topology , SERIES =. 2006 , MRCLASS =

  63. [63]

    Ozsv\'. On the. Adv. Math. , FJOURNAL =. 2005 , NUMBER =. doi:10.1016/j.aim.2004.05.008 , URL =

  64. [64]

    Ozsv\'. Knot. Topology Appl. , FJOURNAL =. 2004 , NUMBER =. doi:10.1016/j.topol.2003.09.009 , URL =

  65. [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. [66]

    Reshetikhin, Nikolai and Turaev, Vladimir , TITLE =. Comm. Math. Phys. , FJOURNAL =. 1990 , NUMBER =

  67. [67]

    1994 , PAGES =

    Turaev, Vladimir , TITLE =. 1994 , PAGES =

  68. [68]

    Stoimenow, Alexander , TITLE =