How Karatsuba’s algorithm gave us new ways to multiply

To advance the field of computer science, mathematician Kolmogorov tried to optimise the multiplication algorithm we learn in elementary school. After failing to do so, he conjectured that no faster algorithms exist. This gave rise to Karatsuba’s fast multiplication algorithm, an algorithm named after Anatoly Karatsuba that is faster than the elementary school algorithm. This video gives an introduction to theoretical computer science and Kolmogorov’s conjecture, explains the algorithm, proves that it has a runtime faster than quadratic, and goes over the history of multiplication algorithms that came afterwards. 0:00 Theoretical Computer Science 5:25 Kolmogorov 7:34 Karatsuba 15:12 The Post-FFT Era