Speaker: Olga V. Holtz, University of California, Berkeley

Ever since the invention of the first algorithms, mathematicians wondered how 'complex' such computational procedures are. This talk will offer an excursion into the world of complexity. How fast can we determine if a given number is prime, find the greatest common divisor of two
polynomials, or multiply two matrices? What problems are solvable in polynomial time? What are randomized algorithms and how complex are they? What is communication complexity? And why should we care whether or not P equals NP?