Theorem

You can project n points into O(log n / eps^2) dimensions and keep every distance. The theorem underneath every vector database.

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

PAC learning and VC dimension's bounds predict that an overparameterized network cannot generalize, and it generalizes anyway.

Averaged over all problems under a uniform measure — a distribution no real task is drawn from — every learner ties.

Error splits into three terms, one of which is irreducible. Still the right first diagnosis of a bad model.

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

No ranked voting system satisfies a short list of obviously reasonable conditions. Applies directly to prioritization, ranking, and consensus UX.

A stable matching always exists and is findable in O(n^2), but it's optimal for the proposing side. Mechanism design in twenty lines.

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

Every optimization problem has a shadow problem whose optimum is the same number, and it certifies your answer: the only post in the series about proving your...

The bottleneck equals the capacity, exactly. A duality result you can see, and the workhorse behind matching and segmentation.

The constant factors that dominate asymptotics in practice, and cache-oblivious algorithms as the theoretical response.

The unimplementable best cache policy, and the proof that LRU is k-competitive with it. The application of Competitive analysis and ski rental, so it follows it.

How to reason about decisions made without the future, with a provable ratio. Rent-vs-buy shows up in caching, autoscaling, and connection pooling.

Rate limiting has a theory: bound the arrival curve and you get a provable bound on delay and queue depth.

The M/M/1 queue's 1/(1-rho) blowup. Why a service at 80% load is fine and at 95% is on fire.

L = lambda W, with essentially no assumptions. Capacity planning from one line of algebra.

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

Security lives in the key; and Shannon's proof that the one-time pad is unbreakable and impractical for the same reason.

O(log n) proof that one item belongs to a huge set. Git, certificate transparency, and every blockchain are the same data structure.