Return to Colloquia & Seminar listing
Geometric topology meets computational complexity
Faculty Research Seminar| Speaker: | Greg Kuperberg, UC Davis |
| Location: | Zoom |
| Start time: | Tue, Mar 2 2021, 12:10PM |
I will discuss the currently progressing research topic of computational complexity of geometric topology problems. How difficult is it to distinguish the unknot? Or 3-manifolds from each other? The right approach to these questions is not just to consider quantitative complexity, i.e., how much work they take for a computer; but also qualitative complexity, whether there are efficient algorithms with one or another kind of help. I will discuss various results on this theme, such as that knottedness and unknottedness are both in NP; and I will discuss high-dimensional questions for context.