On July 1, Emory University mathematician Hao Huang quietly proved a theorem — and the mathematics and computer science worlds roared. In an elegant argument, laid out over six pages, Huang unequivocally proved the sensitivity conjecture, a thorn in the side of computer scientists for decades.
The proof ignited the mathosphere. “Amazingly short and beautiful,” blogged Gil Kalai, a mathematician at the Hebrew University of Jerusalem. The proof “shows that people can still find simple proofs of deep, open questions,” says Cris Moore, a computer scientist and mathematician at the Santa Fe Institute.
A long line of thinkers over nearly 30 years have tangled with the problem. But until Huang came along, it remained a mathematical itch that no one could scratch — everyone knew where it was, but they just couldn’t reach it.
The conjecture relates to mathematical structures called Boolean functions, which convert multiple binary inputs — 0s and 1s, for example, or “trues” and “falses” — into a single binary output. You might flip a coin 10 times and define a Boolean function to output a “1” if you get at least one head, and a “0” otherwise.
It may seem abstract, but Boolean ideas are essential for today’s technological landscape, because they make it possible for computers to compute. Transistors are basically on/off switches with only one of two values. But computer scientists wanted to know more about the complexity of these functions. For example: At a given step in the function, how many inputs would you have to flip to change the output? The numerical answer to this question — that is then extended to the entire function, roughly speaking — is called the sensitivity.
Sensitivity is special. Other ways to gauge complexity of Boolean functions exist, but they’re all known to be related to each other mathematically. Sensitivity, though, has always been an outlier. The sensitivity conjecture, basically, describes how this measure could fit into the mathematical family. It made sense that it should be included, but actually proving how it belonged was a trickier matter.
Huang says the problem’s deceptive simplicity first piqued his interest in 2012. “Every time I decided to pick it up again, I would spend three or four days and go nowhere,” he says. “That’s my approach to a lot of problems.” He thinks he spent hundreds of hours on it over the years.
Huang’s breakthrough came last June on a warm night in Madrid, where he was holed up in a hotel room with a noisy air conditioner. He should have been finishing a tortuous grant application, but instead, he found himself thinking again about sensitivity. Like other mathematicians before him, he thought the most natural way to work with the binary inputs of Boolean functions was to treat them as coordinate points, the corners of an imaginary kind of high-dimensional cube. Twenty-seven years ago, a mathematician and a computer scientist showed that if you take a set of at least half of these points and could find connections between them, you could then prove the sensitivity conjecture. And that’s what Huang did: He used tools from the field of linear algebra to prove that 1992 statement. Afterward, he wrote up his work, posted it online, and experts marveled equally at his proof’s unequivocal argument and its compact, elegant structure.
Huang isn’t surprised it took a mathematician to crack the computer science problem. “Theoretical computer science is abstract mathematics,” he says, and this problem shows the connection. “Computer scientists often need problems to have applications, but for us mathematicians, we care about elegance, and whether the problem can be stated nicely.”
