We describe an efficient algorithm to compute finite type invariants of type $k$ by first creating, for a given knot $K$ with $n$ crossings, a look-up table for all subdiagrams of $K$ of size $\lceil \frac{ k}{ 2}\rceil$ indexed by dyadic intervals in $[0,2n-1]$. Using this algorithm, any such finite type invariant can be computed on an $n$-crossing knot in time $\tilde{ O}( n^{ \lceil \frac{ k}{ 2}\rceil})$, a lot faster than the previously best published bound of $\tilde{ O} (n^k)$.
Categories: math.GT