Happens-Before and Lamport Clocks
There is no global "now"; causality is the only ordering you get. The foundational conceptual shift of the whole part.
Posts
Parameterized Complexity (FPT and W[1])
"NP-hard" hides that some hard problems are easy when one parameter is small. The most practically useful refinement of Karp's 21 problems.
Approximation Algorithms and Ratios
The positive side: 2-approximate vertex cover, PTAS, and where the approximability cliff sits.
The PCP Theorem and Inapproximability
Every proof can be checked by reading three bits, and therefore some problems are hard even to approximate.
Streaming Lower Bounds and Sketching
Exact distinct-count needs linear space; approximate needs almost none. HyperLogLog and Count-Min as the constructive half.
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".
The Barriers: Relativization and Natural Proofs
Why P vs NP has resisted for fifty years, stated as two theorems about which proof techniques cannot work.
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.
P vs NP
Verifying vs finding. State it properly, including what a proof either way would actually change.
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...
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.
The Coffman Conditions
Four conditions, all necessary for deadlock; break any one. The cleanest example of a characterization theorem doing engineering work.
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.