information
The noisy channel's limit
It is 1948 at Bell Labs, and the question is whether noise sets a hard ceiling on communication or merely a nuisance you can shrink with effort. A channel flips each transmitted bit with probability 0.1. Determine the maximum rate at which information can be sent over it with error driving to zero — and, astonishingly, prove that this rate is actually achievable, that reliable communication through an unreliable channel is possible right up to a precise limit. This number is a law of nature for information. Get it wrong and engineers either despair of noisy channels they could have used to the hilt, or chase rates above capacity where no code can ever be reliable — the capacity theorem drew the line that all of modern communication lives beneath.
Who this problem belongs to
The two figures whose methods fit it best, out of 37 in contention.
This is Shannon's own 1948 result, published at Bell Labs in the very year and building the problem describes. 'A Mathematical Theory of Communication' defines channel capacity C = max I(X;Y), computes it for the binary symmetric channel as 1 - H(p) — about 0.531 bits per use at p = 0.1 — and proves via his random-coding argument that any rate below C is achievable with error probability driven to zero, while rates above are not. The proof technique itself, averaging over randomly drawn codebooks and using typical sequences, is his invention and remains the standard method taught today. No other figure in the roster stands closer: the problem is not merely in his field, it is his theorem, at his institution, on his desk, in his notation.
Cover spent his career at Stanford refining, generalizing, and teaching exactly this theorem. Elements of Information Theory (with Joy Thomas, 1991) contains the modern canonical proof: joint typicality decoding, the asymptotic equipartition property, and the converse via Fano's inequality — cleaner machinery than Shannon's 1948 original. Cover extended capacity results to broadcast channels (1972), one of the founding problems of multi-user information theory, so proving achievability and converses for noisy channels was his daily craft. The era gap runs in his favor: he inherits four decades of polished technique Shannon lacked, and would dispatch the binary symmetric channel as a first exercise before proving stronger statements — error exponents, strong converses — that 1948 could not yet state. Only the originator himself outranks him here.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
37 figures are scored on this problem. Draw it in a battle to see where you land.