CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Math Colloquium
Greg Kuperberg
University of California, Davis
Title: Geometric Topology Meets Computational Complexity Greg Kuperberg, UC Davis

Abstract: Now that the geometrization conjecture has been proven, and the virtual Haken conjecture has been proven, what is left in 3-manifold topology? One remaining topic is the 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.

Date: Wednesday, February 21, 2018
Time: 4:30 pm
Location: Wean Hall 8220
Submitted by:  Bukh
Note: Refreshments at 5:30 pm, Wean Hall 6220.