Streaming Lower Bounds and Sketching
Exact distinct-count needs linear space; approximate needs almost none. HyperLogLog and Count-Min as the constructive half.
L2
Universal Hashing
What a hash function actually guarantees, as opposed to what it seems to do.
Minimum Description Length and Occam's Razor
Simplicity, formalized as compression; the bridge from information theory to model selection in PAC learning and VC dimension.
Kolmogorov Complexity
The length of the shortest program producing a string. Uncomputable, and the correct definition of "random" and "simple".
Karp's 21 Problems
Thousands of unrelated-looking problems are secretly the same problem.
The Cook–Levin Theorem
SAT is NP-complete: circuits encode computation. The technical heart of the whole field.
The Hamming Bound and Error-Correcting Codes
How many errors you can fix given how much you're willing to pay in redundancy.
Huffman Coding Is Optimal
And the proof is an exchange argument you can follow. Opens with Kraft (The Kraft inequality and prefix codes): which length assignments exist at all, then which...
Balls Into Bins and the Power of Two Choices
Random placement gives max load ~log n / log log n; picking the emptier of two random bins collapses it to log log n.
Reductions
"Solve A by solving B" is how undecidability and hardness both spread. The mechanical skill behind Parts II and IV.
Godel's Incompleteness Theorems
Any sufficiently strong consistent system has true statements it can't prove, and can't prove its own consistency.
Kleene's Recursion Theorem
Any program can obtain its own source. Quines aren't a party trick; self-reference is guaranteed by the model.
Concentration Bounds (Chernoff/Hoeffding)
Averages of independent things are exponentially unlikely to stray.
Amortized Analysis and the Potential Method
Why a dynamic array's O(n) resize is still O(1) per push, and how to prove it rather than hand-wave it.
Adversary Arguments
Lower bounds by playing against the algorithm: finding max and second-max needs n + ceil(log n) - 2 comparisons.
The Omega(n log n) Comparison-Sort Bound
A decision tree with n! leaves must be log(n!) deep, and log(n!) = Theta(n log n) by the (n/2)^(n/2) trick — the one step that costs this post its L1.
Shannon Entropy and the Source Coding Theorem
Entropy is the exact floor on lossless compression. Where "information" stops being a metaphor.
Rice's Theorem
Every non-trivial semantic property of programs is undecidable.
Gustafson's Law and the Universal Scalability Law
Amdahl's rebuttal, and then the law that adds a negative term for coordination: past a point, more nodes make it slower.