Talk:Computational topology
![]() | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
Plans
[edit]I'd like to revise this page to bring it more in-line with contemporary usage of the phrase computational topology. This will likely mean the spawning of various associated pages, such as algorithmic 3-manifold theory, knot theory, algebraic topology, etc. This is partially an attempt to find an appropriate venue for these ideas: http://mathoverflow.net/questions/35946/how-expensive-is-knowledge-knots-links-3-and-4-manifold-algorithms Rybu (talk) 19:55, 18 August 2010 (UTC)
Missing algorithm details
[edit]Here are a few things I'd like to see eventually make it into the article.
- I'm aware there's a version of the Manning algorithm for cusped hyperbolic manifolds. Due to Tillman and maybe Schleimer? I've heard it should be publisted as part of the JacoFest proceedings. Rybu (talk)
- Run-time estimates on Jones, HOMFLYPT from planar knot/link diagrams. Do computations benefit from a quantum computer?
- Dynnikov's work on unknot recognition.
- Are there run-time estimates on how long it would take to determine if a knot is slice? ribbon?
These questions all assume triangulations as input.
- The connect-sum decomposition? (Jaco, Rubinstein, Burton, etc)
- How expensive is the compression-body decomposition, and the JSJ-decomposition?
- How expensive is hyperbolisation (for a triangulated, hyperbolisable 3-manifold) i.e. the closed+cusped Manning algorithm. (Manning, ?Tillman?, others?)
- How expensive is geometrization? (?)
- How expensive is it to compute the Alexander ideals of a triangulated 3-manifold?
- How expensive is it to produce a surgery presentation of a 3-manifold from a triangulation? (D.Thurston and Costantino's work is the closest related to this that I know -- partially written up)
- Given an ordinal $n$ representing the volume of a hyperbolic $3$-manifold of finite volume, I want to know the actual volume (as a real number). How difficult is that to know? How about reconstructing the 3-manifold as well?
- Given a triangulated cusped hyperbolisable $3$-manifold, is there an efficient algorithm to construct the Epstein-Penner decomposition?
- Given a triangulated rational homology 3-sphere, how expensive is it to compute the generalized Rochlin invariant? (or the Rochlin invariant for a homology 3-sphere)
- Same question, but given a surgery presentation for the rational homology 3-sphere. In this case there is the Kaplan algorithm.
- What computable invariants of Farber-Levine pairings are there, and how hard are they to compute from a surgery presentation of a triangulation of a 4-manifold?
- Is the Oszvath-Szabo d-invariant of $spin^c$ rational homology spheres algorithmically computable now, given a surgery presentation? How are run-times?
Rybu (talk) 23:01, 18 August 2010 (UTC)
Recent edits on lambda calculus
[edit]User Samuel Lev has appended notes on "The computational topology" from lambda calculus, which is completely unrelated to the subject of Computational Topology. I would like to suggest he start another page and perhaps a disambiguation page if it's really necessary. I doubt people would generally confuse the two. Rybu (talk) 04:44, 5 June 2012 (UTC)