# MSCS Seminar Calendar

Friday August 28, 2015

Wednesday September 16, 2015

**Geometry, Topology and Dynamics Seminar**

Knottedness is in NP, modulo GRH

Greg Kuperberg (UC Davis)

3:00 PM in SEO 636

In this talk I will discuss my result that confirming that a knot diagram is a non-trivial knot is in the complexity class NP, assuming the Generalized Riemann Hypothesis. Time permitting, I will also discuss related results, in particular the earlier result of Hass, Lagarias, and Pippenger that unknottedness is in NP. Everything will be on the theme of qualitative complexity theory in geometric topology, in other words, what you can compute in polynomial time with help.

Thursday September 17, 2015

**Quantum Topology / Hopf Algebra Seminar**

How hard is it to approximate the Jones polynomial?

Greg Kuperberg (UC Davis)

3:00 PM in SEO 612

The short answer is that it's #P-hard. The longer answer
is that it was an algorithm was constructed in the quantum computation
community to approximate the Jones polynomial at a principal root of
unity, except with a diagram-dependent normalization factor. I will
present my result that if you strip away this normalization factor to
ask for any fair approximation, then approximating the Jones
polynomial is as hard as any combinatorial counting problem and almost
certainly out of reach for classical or even quantum computers. It
is conjectured that the Jones polynomial distinguishes the unknot, but
we can envision that we can know whether a complicated knot diagram is
an unknot long before we know much about its Jones polynomial.

Monday October 5, 2015