information
Can these codeword lengths even exist?
It is the foundational moment of coding theory, and before you can build good codes you must answer a prior question: given a wishlist of codeword lengths, does a prefix-free code with those lengths exist at all? You cannot make every codeword short — brevity for one symbol steals possibility from others, and there is an exact budget. Prove the inequality that decides feasibility, show it necessary and sufficient, and draw the corollary tying minimum expected code length to entropy, so no code beats the bound and one comes within a bit of it. Get it wrong and you chase impossible codebooks or leave achievable compression unclaimed — this inequality is the gate every source code passes, the bridge from entropy to real codes.
Who this problem belongs to
The two figures whose methods fit it best, out of 35 in contention.
Shannon's 1948 'A Mathematical Theory of Communication' proves exactly this result: the source coding theorem establishing that no uniquely decodable code can beat the entropy bound on average length, and that codes achieving within one bit of entropy always exist. The Kraft inequality itself, formalized shortly after by Kraft and McMillan, is the feasibility condition Shannon's construction implicitly relies on, showing precisely which wishlists of codeword lengths admit a prefix-free realization, since giving one symbol a short codeword necessarily consumes probability mass that steals length-budget from others. Shannon built the entire conceptual apparatus, entropy as the fundamental limit, from scratch in one paper. The only reason this is not a full 100 is that the sharp necessary-and-sufficient inequality bears Kraft's and McMillan's names, formalized just after his own foundational proof.
Cover's textbook with Joy Thomas gives the modern, canonical treatment of exactly this material: the Kraft inequality proved as a necessary and sufficient condition for the existence of prefix-free and even general uniquely decodable codes, alongside the tight corollary bounding expected code length between entropy and entropy-plus-one. His own research on universal source coding and the relationship between coding, gambling, and prediction extends this exact machinery into questions of adaptive compression without knowing the source distribution in advance, showing his fluency runs well past textbook exposition into original contribution. He is not scored above Shannon because the foundational theorem and its use are Shannon's; Cover's contribution is the definitive systematization, extension, and generalization of that proof for later generations.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
35 figures are scored on this problem. Draw it in a battle to see where you land.