Computing finite type invariants efficiently
Dror Bar-Natan, Itai Bar-Natan, Iva Halacheva, Nancy Scherich · Proceedings of the American Mathematical Society · 2026
We describe an efficient algorithm to compute finite type invariants of type k k by first creating, for a given knot K K with n n crossings, a look-up table for all subdiagrams of K K of size ⌈ k 2 ⌉ \lceil \frac {k}{2}\rceil indexed by dyadic intervals in [ 0 , 2 n − 1 ] [0,2n-1] . Using this algorithm, any such finite type invariant can be computed on an n n -crossing knot in time O ~ ( n ⌈ k 2 ⌉ ) {\tilde {O}}(n^{\lceil \frac {k}{2}\rceil }) , a lot faster than the previously best published bound of O ~ ( n k ) {\tilde {O}}(n^k) .