Thurston will speak on:
Title: Stress matrices and rigidity
Abstract: When do the lengths of the edges of a straight-edge framework determine the positions of the vertices? The problem comes up all the time in applications ranging molecular biology to sensor networks to computer vision. But it also turns out that the problem is NP-hard in general. It becomes easier if you require the initial position to be generic; then there is a polynomial algorithm based on the stress matrix of the graph. But even in this case, actually reconstructing the positions from the edge-length is difficult. There is a good algorithm in case the framework is universally rigid: the edge lengths determine the framework independently of the embedding dimension. There is again a characterization of such frameworks in terms of the stress matrix. This is joint work with Steven Gortler and Alex Healy.
Dunfield will speak on:
Title: The least spanning area of a knot and the Optimal Bounding Chain Problem
Abstract: Two fundamental objects in knot theory are the minimal genus surface and the least area surface bounded by a knot in a 3-dimensional manifold. While these two surfaces are not necessarily the same, when the knot is embedded in a general 3-manifold, the two problems were shown earlier this decade to be NP-complete and NP-hard respectively. However, there is evidence that the special case when the ambient manifold is R^3, or more generally when the second homology is trivial, should be considerably more tractable. Indeed, we show here that the least area surface can be found in polynomial time. The precise setting is that the knot is a 1-dimensional subcomplex of a triangulation of the ambient 3-manifold. The main tool we use is a linear programming formulation of the Optimal Bounding Chain Problem (OBCP), where one is required to find the smallest norm chain with a given boundary. While the OBCP is NP-complete in general, we give conditions under which it can be solved in polynomial time. We then show that the least area surface can be constructed from the optimal bounding chain using a standard desingularization argument from 3-dimensional topology. We also prove that the related Optimal Homologous Chain Problem is NP-complete for homology with integer coefficients, complementing the corresponding result of Chen and Freedman for mod 2 homology.