Talk:Computational topology

Plans

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

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

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]