Integer multiplication in time


In my talk, I will present a recent algorithm for multiplying two -bit integers in time . This resolves Schonhage and Strassen's conjectured upper bound believed to be optimal. Among consequences, let us mention improved bounds on computation time of transcendental functions and constants such as and . This talk is aimed at a general audience and no prior knowledge is assumed.

Note: Joint work with David Harvey (UNSW, Sydney)

Occasion: math colloquium, UCLA, Los Angeles, February 13, 2020

Documents: slideshow, TeXmacs source