Great Ideas in Theoretical Computer Science - Polynomials

Explore polynomials in this 1-hour 15-minute lecture from CMU's "Great Ideas in Theoretical Computer Science" course. Delve into fields, prime power, and polynomial operations including addition, multiplication, and division. Learn about evaluation, interpolation, and fitting polynomials to data. Discover applications in error-correcting codes and the Lagrange interpolation method. Gain insights into theoretical computer science concepts through clear explanations and examples provided by Professor Ryan O'Donnell.

Introduction
Fields
Prime Power
Polynomials
Adding and multiplying polynomials
Division of polynomials
Division with remainder
Example
Recap
Evaluation
Theorem
Potential Theorem
Interpolation
Fitting a polynomial to data
Two things to prove
Proof number two
Lagrange interpolation
How it works
Special case
General problem
Error correcting codes
Erasers
Repetition Code