How a Mathematician Solved a Problem That Puzzled Computer Scientists for 30 Years | The Sciences - Discover Magazine

#28 in our top science stories of 2019. 

Mathematician Hao Huang.
Photo: Kay Hinton/Emory University.

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

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.”
Read more...

Source: Discover Magazine