Posts

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

Erasing one bit costs kT ln 2 joules, unavoidably. The point where information theory becomes physics.

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.

Essential vs accidental complexity, and why adding people to a late project makes it later.

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.

Functions belong at the endpoints; lower layers can only optimize, never guarantee. The single most useful design principle in networking.

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.

Least privilege, fail-safe defaults, economy of mechanism; plus the confused deputy as the canonical violation.

A compiler can hide a backdoor in itself with no trace in any source. The limit of source-code review, and what reproducible builds do about 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.