computability
How many bits must cross the wire
It is 1979, and a new lens on difficulty appears: forget time and memory, and ask how much two parties, each holding half the input, must communicate to compute a joint function. Alice has one number, Bob another; how many bits must pass between them to decide if the numbers are equal, or compute their combined answer? Prove tight lower bounds on this communication, independent of how clever either party is locally, and show how those bounds imply limits everywhere they surface — circuit depth, data streams, distributed systems. The abstraction is the invention. Get it wrong and you optimize the wrong resource — grinding locally while the bottleneck is the wire — or miss that a communication lower bound has fenced off a class of algorithms.
Who this problem belongs to
The two figures whose methods fit it best, out of 42 in contention.
Yao is the originator. His 1979 paper 'Some Complexity Questions Related to Distributive Computing' introduced the communication complexity model precisely as this problem describes: two parties, Alice and Bob, each holding part of the input, must determine how many bits they need to exchange to jointly compute a function, independent of local computational power. He proved foundational lower bounds, including for equality testing, and developed Yao's principle, a minimax technique for proving randomized communication lower bounds that remains a standard tool in the field. No one on this roster is closer to having personally invented the exact model, the exact question, and foundational answers this problem asks about; the abstraction genuinely is his invention.
Shannon's 1948 information theory established channel capacity as the fundamental measure of how much information can be reliably transmitted, and his entire intellectual project was measuring communication cost in precise, provable, information-theoretic terms — the direct conceptual ancestor of Yao's 1979 communication complexity model, which asks the analogous question for interactive, function-computing communication rather than one-way transmission. Shannon's framework for quantifying information gives this problem's central question — how many bits must cross the wire — its very vocabulary and mathematical seriousness. He died decades before Yao's specific model existed and never worked on the two-party, function-computation formulation himself, but no one supplied more of the conceptual and mathematical foundation for treating communication cost as a rigorously provable quantity.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
42 figures are scored on this problem. Draw it in a battle to see where you land.