58 DISCOVERMAGAZINE.COMKAYHI
NT
ON/EMOR
Y^ UNIVER
SITYCircuit Sensitivity Is All in
the (Mathematical) Family
BY STEPHEN ORNES28
i
On July 1, Emory University mathe-
matician 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. It “shows that
people can still find simple proofs of deep,
open questions,” says Cristopher Moore,
a computer scientist and mathematician
at the Santa Fe Institute.
A long line of thinkers over nearly
30 years has tangled with the problem.
But until Huang came along, it remained
a mathematical itch that no one could
scratch.The conjecture relates to mathemati-
cal 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.
Boolean ideas are essential for today’s
technological landscape, because they
make it possible for computers to com-
pute. 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 func-
tion, 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.Mathematician Hao Huang