Mathematics Graduate Students Organization

Seminar:

Date: November 10

The last century has witnessed the birth, rapid growth and evolution of the theory of computation and complexity. In this talk we will provide a gentle introduction into these fields with an eye toward their mathematical underpinnings. We will begin in the classical realm of Turing machines and boolean logic and migrate the quantum universe where physical systems have wildly different behavior. The unique phenomena present in the sphere quantum mechanics give rise to unique and powerful computational paradigms which we will explore. Finally, an account of Shor's polynomial time algorithm for integer factorization will be given and recent advances in the field will be discussed. While a background in computation, complexity, and/or quantum mechanics may serve to elucidate the finer points no knowledge of these subjects is assumed.