Mathematics Colloquia and Seminars

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.