SMS scnews item created by Leo Tzou at Tue 30 Apr 2019 1148
Type: Seminar
Distribution: World
Expiry: 30 Oct 2019
Calendar1: 7 May 2019 1200-1300
CalLoc1: UNSW Red Centre 4082
CalTitle1: Integer multiplication in time O(n log n)
Auth: [email protected] (ltzo2369) in SMS-LDAP

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.

Actions:

Calendar (ICS file) download, for import into your favourite calendar application

UNCLUTTER for printing

AUTHENTICATE to mark the scnews item as read