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: leo@1.157.197.244 (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