41
votes
What part is left unsolved in the Unknotting problem? (after results of Bar-Natan, Khovanov, Kronheimer and Mrowka)
To strengthen Sam Nead's answer, note that it is trivial to compute the Jones polynomial from the Khovanov homology. It is known that computing (or even approximating) the Jones polynomial is #P-hard:
...
- 10k
39
votes
Accepted
What part is left unsolved in the Unknotting problem? (after results of Bar-Natan, Khovanov, Kronheimer and Mrowka)
EDIT: Marc Lackenby has just announced a quasi-polynomial time algorithm. That is, given an $n$—crossing diagram, the algorithm takes $n^{O(\log(n))}$ time to either find a spanning disk (proving the ...
- 26.4k
36
votes
Accepted
Reference on Persistent Homology
Since this area is developing rather quickly, there is a dearth of canonical references that would satisfy basic pedagogical requirements. If I were teaching a course on this material right now, I ...
- 15.5k
31
votes
Accepted
Why is persistent cohomology so much faster than persistent homology
There are several factors contributing to the improved performance of the algorithm reported in the paper; the use of cohomology is one, but there is also a computational shortcut involved, and the ...
- 484
24
votes
What part is left unsolved in the Unknotting problem? (after results of Bar-Natan, Khovanov, Kronheimer and Mrowka)
This isn't directly what you ask, but it's also worth noting that unknot detection is in $\text{NP} \cap \text{co-NP}$, that is, there are polynomial-checkable certificates that will show that either ...
- 10k
19
votes
Accepted
Vietoris-Rips complex homology of a higher degree than the ambient dimension
I have examples for $\ell_2$ distance in $\mathbb{R}^2$.
In particular, take $2n+2$ points at the vertices of a regular polygon of unit radius, and set the distance parameter to be slightly less than ...
- 12.2k
13
votes
Is there an algorithm for the genus of a knot?
There is an algorithm using normal surface theory, originally developed by Haken and Schubert to compute the genus of any knot. These articles are in German, but for a reference in English, one could ...
- 1,617
13
votes
Accepted
Is there an algorithm for the genus of a knot?
Jaco and Oertel's paper An algorithm to decide if a three-manifold is a Haken manifold [1984], plus a bit of work, gives a doubly exponential time algorithm to compute the Seifert genus. (In practice ...
- 26.4k
12
votes
Reference on Persistent Homology
Edelsbrunner and Harer's book seems good.
Edelsbrunner, Herbert; Harer, John L., Computational topology. An introduction, Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4925-5/...
- 95.6k
12
votes
Reference on Persistent Homology
This paper was released on the arXiv just this (12Sep2018) morning:
"A Brief History of Persistence."
Jose A. Perea. 2018.
arXiv abstract.
"Persistent homology is currently one of the more ...
- 149k
11
votes
Accepted
Quantitative word problem for 3-manifold groups
Suppose that $M$ is a compact irreducible 3-manifold.
Assume that $M$ is neither a Nil nor a Sol-manifold. Then $G=\pi_1(M)$ is automatic, which implies that $G$ has quadratic Dehn function and the ...
- 9,748
10
votes
Is being simply connected very rare?
Here's a rough estimate indicating that indeed, in this "bounded-valency" model, a simplicial complex has nonvanishing fundamental group with high probability. We'll actually conclude ...
- 61.6k
10
votes
Accepted
Knot Diffie–Hellman
Here I assume that by “addition” of knots you mean the usual connect sum, as defined here. With that said, I think you correctly ask the relevant question: “Is factoring knots difficult?”
In favour ...
- 26.4k
9
votes
Accepted
Software for computing Thurston's unit ball
"Better late than never." Stephan Tillmann and William Worden have produced the software package tnorm. This can be found here:
https://pypi.org/project/tnorm/
The software should be able ...
- 26.4k
9
votes
Smooth Morse function from Forman's discrete Morse function
You can do the next best think. To a Forman-Morse function $f$ one can associate a flow on the manifold whose stationary points are precisely the barycenters of the faces of your simplicial ...
- 34.1k
8
votes
Accepted
Is there an upper bound on the number of points in point cloud for which we compute the persistent homology?
It depends very much on the type of simplicial complex you're using. If you have points in 3d then doing Cech/Delaunay complex is feasible with millions of points. If you have high dimensional data, ...
- 2,582
8
votes
Reference on Persistent Homology
The book by Steve Oudot is an alternative: Steve Y. Oudot. Persistence Theory: From Quiver Representations to Data Analysis (Mathematical Surveys and Monographs).
There is also a relatively new ...
- 181
8
votes
Accepted
Deep learning for knot theory. Classification
I saw two articles today (12/2/21) that reminded me of this post. I am mentioning them here to potentially help the OP:
Learning knot invariants across dimensions by Jessica Craven, Mark Hughes, ...
- 8,394
7
votes
Reference on Persistent Homology
Maybe the following papers will be useful:
https://www.cambridge.org/core/journals/acta-numerica/article/topological-pattern-recognition-for-point-cloud-data/BB0DA0F0EBD79809C563AF80B555A23C (...
- 16.4k
7
votes
Vietoris-Rips complex homology of a higher degree than the ambient dimension
I hope to see a nicer proof which works for all $d$ or with the Euclidean distance which is surely of much more interest, but in the meantime, here's something ham-handed showing that the answer is no ...
- 13.5k
7
votes
Deep learning for knot theory. Classification
Adding to Sean Lawton's answer, there was an arxiv posting yesterday by Davies-Juhász-Lackenby-Tomasev, The signature and cusp geometry of hyperbolic knots that describes a relation between the cusp ...
- 19.2k
7
votes
Is there an algorithm for the genus of a knot?
I think it's usually easier in practice, but knot Floer homology determines the genus (and is algorithmically computable from a diagram). See Ozsváth and Szabó's paper "Holomorphic disks and ...
6
votes
Is being simply connected very rare?
The following does not answer your question, but adding just in case it is helpful.
If you weaken "simply connected" to $H_1(\Delta, \mathbb{Q}) = 0$, and weaken "every vertex is in a ...
- 7,755
6
votes
Accepted
Properties a triangulation must have in order to describe a manifold
From the comments:
Suppose that $T$ is a triangulation. If all vertex links are PL $(n-1)$-dimensional spheres then the realisation space of $T$ is a PL manifold and thus a topological manifold. (In ...
6
votes
Accepted
Are hyperbolic $n$-manifolds recursively enumerable?
The class of closed hyperbolic manifolds is recursively enumerable. I’ll describe a terrible algorithm which nevertheless gives an enumeration.
A couple of basic facts: a hyperbolic $n$-manifold $M$ ...
- 66.8k
6
votes
Are there any non-elementary functions that are computable?
Obviously the perimeter of an ellipse is a computable function of the parameters (e.g. semi-major and semi-minor axes). What it means for this to be computable is precisely that we can compute ...
- 225k
6
votes
Accepted
Upper bounds on the Gromov–Hausdorff distance using persistent homology
For general $P$ and $Q$, you won't find such a function $g$. For example, if you remove the assumption that $P$ and $Q$ are finite, then you could let $P$ be $\mathbb{R}$ and you could let $Q$ be a ...
- 436
5
votes
Is there an upper bound on the number of points in point cloud for which we compute the persistent homology?
Possibly of interest to you is this paper, A roadmap for the computation
of persistent homology by Otter, Porter, Tillmann, Grindrod, and Harrington. They compare different pieces of software for ...
- 1,149
5
votes
Is there an algorithm for the genus of a knot?
In addition to the references given in the other answers, Lackenby has shown that recognition of the Seifert genus is in NP. This is based on a taut sutured manifold hierarchy for the knot complement ...
- 66.8k
5
votes
Knot Diffie–Hellman
Edit: Thanks to @SamNead, for pointing out that the conjugacy problem is polynomial time, albeit with horrible constants. See video here
There is some literature on Braid group cryptography.
Here is ...
- 10.1k
Only top scored, non community-wiki answers of a minimum length are eligible