Return to Colloquia & Seminar listing

### Computational complexity of orbit and isomorphism problems

**Algebra & Discrete Mathematics**

Speaker: | Greg Kuperberg, Dept. of Mathematics, UC Davis |

Location: | 1147 MSB |

Start time: | Thu, Jan 24 2013, 3:10PM |

I will relate some modern complexity classes, such as P, NP, SZK, and BQP, to orbit and isomorphism problems in algebra and geometry. This investigation is inspired by the famous Shor's algorithm. Shor's algorithm can calculate an orbit of the integers Z in quantum polynomial time (thus, in BQP) in the bit complexity of the period, which is classically impossible. But, assuming standard conjectures in complexity theory, Shor's algorithm cannot be extended to either a non-commutative free group or to the rational numbers Q. If time permits, I will also discuss graph isomorphism and isomoprhism of polynomials and tensors as special orbit problems.