Computing Finite Type Invariants Efficiently
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909709574864896 |
|---|---|
| author | Bar-Natan, Dror Bar-Natan, Itai Halacheva, Iva Scherich, Nancy |
| author_facet | Bar-Natan, Dror Bar-Natan, Itai Halacheva, Iva Scherich, Nancy |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15942 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing Finite Type Invariants Efficiently Bar-Natan, Dror Bar-Natan, Itai Halacheva, Iva Scherich, Nancy Geometric Topology 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)$. |
| title | Computing Finite Type Invariants Efficiently |
| topic | Geometric Topology |
| url | https://arxiv.org/abs/2408.15942 |