Complexity of Basic Arithmetic || @ CMU || Lecture 7a of CS Theory Toolkit

Value of the Information & Strength of the Argument

The lecture provides a clear and rigorous explanation of the complexity of integer multiplication, building from basic addition to advanced FFT-based methods. The argumentation is solid, with careful attention to computational models (word RAM) and the distinction between arithmetic operations and time complexity. The lecturer effectively motivates the topic by connecting it to cryptography and other arithmetic problems, and he presents a coherent narrative from the schoolbook algorithm to linear-time multiplication. The discussion of historical developments and the reduction of other arithmetic operations to multiplication adds depth and demonstrates the central role of multiplication in computational complexity.

The title accurately reflects the content: a lecture on the complexity of basic arithmetic operations, focusing on integer multiplication.

8/10

Lecture by a recognized CS theory professor at CMU, covering established results with references to Knuth and Brent & Zimmermann. The content is technically accurate and well-structured, though it is a lecture rather than peer-reviewed material.

Markers derived by PSI from the transcript: the creator did not define chapters.

• 00:00Introduction to the lecture topic: time complexity of basic arithmetic operations, focusing on multiplication.
• 01:00Discussion of addition of n-bit numbers and the word RAM model.
• 03:00Explanation of the schoolbook multiplication algorithm and its quadratic time complexity.
• 05:00Introduction of the discrete Fourier transform (DFT) method for multiplication.
• 07:00Historical note: Gauss discovered the FFT in 1805, later credited to Cooley and Tukey.
• 10:00Discussion of the FFT algorithm and its O(n log n) arithmetic operations.
• 12:00Implementation of FFT on the word RAM model, achieving O(n log n) time.
• 15:00Derivation of linear-time multiplication on the word RAM model.
• 18:00Overview of other arithmetic operations that reduce to multiplication (division, square roots, GCD, etc.).
• 20:00Mention of the Schönhage-Strassen algorithm and later improvements.

• The Art of Computer Programming, vol. 2, chap. 4.3.3 — Referenced as a resource for integer multiplication algorithms.
• Modern Computer Arithmetic — Referenced as a resource for arithmetic algorithms and reductions.
• Course homepage on CMU's Diderot system — Course materials and resources.
• Ryan O'Donnell's homepage — Instructor's academic page.

• The Art of Computer Programming, vol. 2 — Knuth's classic reference on arithmetic algorithms, cited in the lecture.
• Modern Computer Arithmetic — Brent and Zimmermann's book, cited as a resource for arithmetic algorithms.

• www.panopto.com
• www.rebeccakphoto.com