Talk:Computational topology

Latest comment: 11 years ago by Rybu in topic Recent edits on lambda calculus

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)Reply

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)Reply

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)Reply