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 |
Description
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.