Joint Colloquium: David Harvey -- Integer multiplication in time O(n log n)

Joris van der Hoeven and I recently discovered an algorithm that computes the product of
two n-bit integers in O(nlogn) bit operations.  This is asymptotically faster than all
previous known algorithms, and matches the complexity bound conjectured by Schönhage
and Strassen in 1971.  In this talk, I will discuss the history ofinteger
multiplication, and give an overview of the new algorithm.  No previous background on
multiplication algorithms will be assumed.