The computational complexity of geometric topology problems 



Greg Kuperberg

Monday, September 23, 2013
4:00pm 5130
Upson Hall



I will survey some of the results and questions about the complexity of geometric topology problems, specifically in the sense of complexity classes.  What is the complexity of distinguishing n-manifolds for various n?  Of distinguishing knots?  Of recognizing a sphere, or the unknot? Last but not least I will discuss some of my own contributions:  Unknot and 3-sphere recognition are in coNP assuming the RIemann hypothesis; approximating the Jones polynomial is #P-hard; and complexity results for certain higher-dimensional problems.