Decades-Old Computer Science Conjecture Solved in Two Pages

Erica Klarreich in Quanta:

The mathematician Hao Huang during a recent vacation in Lisbon.

paper posted online this month has settled a nearly 30-year-old conjecture about the structure of the fundamental building blocks of computer circuits. This “sensitivity” conjecture has stumped many of the most prominent computer scientists over the years, yet the new proof is so simple that one researcher summed it up in a single tweet.

“This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science,” wrote Scott Aaronson of the University of Texas, Austin, in a blog post. “The list of people who tried to solve it and failed is like a who’s who of discrete math and theoretical computer science,” he added in an email.

The conjecture concerns Boolean functions, rules for transforming a string of input bits (0s and 1s) into a single output bit.

More here.  [Thanks to Ali Minai.]