Landauer's Principle
Erasing one bit costs kT ln 2 joules, unavoidably. The point where information theory becomes physics.
Information-Theory
The No-Cloning Theorem
An unknown quantum state cannot be copied, and the two-line proof is just linearity.
The Nyquist–Shannon Sampling Theorem
Sample above twice the bandwidth or lose information irrecoverably.
Streaming Lower Bounds and Sketching
Exact distinct-count needs linear space; approximate needs almost none. HyperLogLog and Count-Min as the constructive half.
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".
The Hamming Bound and Error-Correcting Codes
How many errors you can fix given how much you're willing to pay in redundancy.
The Noisy-Channel Coding Theorem
You can communicate at capacity with arbitrarily low error. Shannon's most surprising result: reliability is free below the limit.
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...
Shannon Entropy and the Source Coding Theorem
Entropy is the exact floor on lossless compression. Where "information" stops being a metaphor.
No Universal Lossless Compressor
Any algorithm that shrinks some inputs must grow others. Kills every "compresses random data" claim on sight.