Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.