L3

An exponential speedup for factoring and discrete log, killing RSA and ECC; and only a square root for unstructured search, which is why symmetric crypto survives...

How much data you need is a function of hypothesis-class complexity, not of the data. Generalization, made a theorem.

The exact structural condition under which greedy is provably correct. Answers "when can I just be greedy?" once and for all.

Convince someone you know a secret while revealing nothing. The most counterintuitive constructive result in the series.

Atomic registers cannot implement consensus for two threads; compare-and-swap does it for any number. Why your CPU has CAS.

Exhaustively verifying concurrent systems by turning "always eventually" into an automaton, and the state-explosion wall.

Sound approximation, made rigorous. The principled answer to the tradeoff Rice's theorem forces on you.

Interaction plus randomness lets a prover convince you of things you could never check alone.

A program can be coordination-free iff it's monotone. The positive result hiding behind all the impossibility ones.

Randomness probably doesn't add power; the surprise is that hardness is what buys you fake randomness.

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...

No deterministic consensus in an asynchronous system with one crash fault. The rigorous theorem that CAP only gestures at.

Every proof can be checked by reading three bits, and therefore some problems are hard even to approximate.

Why P vs NP has resisted for fifty years, stated as two theorems about which proof techniques cannot work.

You can communicate at capacity with arbitrarily low error. Shannon's most surprising result: reliability is free below the limit.