| Computer Science/Discrete Mathematics Seminar I | |
| Topic: | The Computational Complexity of Geometric Topology Problems |
| Speaker: | Greg Kuperberg |
| Affiliation: | University of California, Davis |
| Date: | Monday, September 24 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
This talk will be a partial survey of the first questions in the complexity theory of geometric topology problems. What is the complexity, or what are known complexity bounds, for distinguishing n-manifolds for various n? For distinguishing knots? For recognizing a sphere, or the unknot? The survey will be a warmup to my own contribution, which is the fact that knottedness is in NP, assuming the generalized Riemann hypothesis.