What I'm reading this evening: "The Pachner graph and the simplification of 3-sphere triangulations", by Benjamin Burton, arXiv:1011.4169. He posted it last November, but revised it again recently and somehow the revision caught my attention after the original posting didn't. It's also one of the papers included in the recently posted list of SoCG acceptances.

The basic problem it deals with is trying to tell different three-dimensional spaces apart from each other, and in particular how to distinguish the three-sphere (a space that can be formed from the familiar Euclidean space by adding a single "point at infinity") from other topological spaces.

The spaces given as input to the problem are described as a set of tetrahedra together with a pattern for gluing their faces together, and one way to solve this in practice is to perform flips (local operations that change the set of tetrahedra without changing the topological type of the input) until reaching a simplified and recognizable gluing pattern. It's known that repeated flipping from any topological 3-sphere can eventually reach a canonical triangulation that consists a single tetrahedron glued to itself, but it's not always possible to do this using flips that decrease the number of tetrahedra — sometimes one has to increase the number of tetrahedra before decreasing it again.

What Burton does is to implement and test this algorithm on approximately 31 million different 9-tetrahedron complexes. He shows that, in these cases, all of the local minima in the flip graph are shallow: one only ever needs to increase the number of tetrahedra by two to find a path to the global minimum. This is in strong contrast to proven superexponential upper bounds on the number of additional tetrahedra.

Burton's results are consistent with past experience with programs like SnapPea, suggesting that these problems are a lot easier in practice than our current theory tells us, and they're enough for him to make some conjectures that, if true, would imply that 3-sphere recognition could be solved in polynomial time.