Plug your ears! Graph isomorphism, siren of the algebraic seas, calls to your quantum helmsman.

Computer Science/Discrete Mathematics Seminar II
Topic:Plug your ears! Graph isomorphism, siren of the algebraic seas, calls to your quantum helmsman.
Speaker:Alex Russell
Affiliation:University of Connecticut
Date:Tuesday, October 2
Time/Room:10:30am - 12:30pm/S-101

Shor's algorithm, the hallmark quantum algorithmic breakthrough, has been successfully generalized to address a variety of related algebraic problems. Generalizations to nonabelian settings could have striking consequences, but such efforts have been systematically frustrated. This talk describes a rigorous obstruction to such natural generalizations and the connection to Graph Isomorphism. Along the way, we will give a friendly introduction to one of the gems of 19th century mathematics: the representation theory of finite groups.