The CALM Theorem and CRDTs
A program can be coordination-free iff it's monotone. The positive result hiding behind all the impossibility ones.
Theorem
The CAP Theorem and PACELC
What it actually says, why it's routinely misquoted, and why latency (the "ELC") is the part that governs real designs.
Paxos, Raft, and the Shape of Consensus
How real systems dodge FLP impossibility: safety always, liveness only when the network cooperates.
Quorum Intersection (R + W > N)
One inequality generating the entire read/write consistency tradeoff space.
The Myhill–Nerode Theorem
A language is regular iff it has finitely many distinguishable prefixes; and this gives you the unique minimal DFA.
Kleene's Theorem: Regexes Are Finite Automata
Two very different-looking formalisms, exactly the same power. Explains how a regex engine really works.
BPP, Pseudorandomness, and Derandomization
Randomness probably doesn't add power; the surprise is that hardness is what buys you fake randomness.
Parity Is Not in AC^0
An actual, unconditional circuit lower bound. Proof that lower bounds are possible at all, which is what stops The barriers: relativization and natural proofs from...
The Nyquist–Shannon Sampling Theorem
Sample above twice the bandwidth or lose information irrecoverably.
The Byzantine Generals Problem
You need 3f+1 nodes to tolerate f liars, and that bound is tight.
FLP Impossibility
No deterministic consensus in an asynchronous system with one crash fault. The rigorous theorem that CAP only gestures at.
Vector Clocks and Causal Consistency
Detecting concurrency exactly, at the cost of O(n) metadata. The tradeoff every eventually-consistent store makes.
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.
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".