Communications of the ACM
Mathematician Solves Computer Science Conjecture in Two Pages
Hao Huang says "I became really obsessed" with the sensitivity conjecture in late 2012.
Credit: Quanta Magazine
A 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 conjecture concerns Boolean functions. Every computer circuit is some combination of Boolean functions, making them "the bricks and mortar of whatever you're doing in computer science," said Rocco Servedio of Columbia University.
Over the years, computer scientists have developed many ways to measure the complexity of a given Boolean function. Each measure captures a different aspect of how the information in the input string determines the output bit. Yet computer scientists have found that nearly all these measures fit into a unified framework, so that the value of any one of them is a rough gauge for the value of the others. Only one complexity measure didn't seem to fit in: sensitivity.
Now Hao Huang, a mathematician at Emory University, has proved the sensitivity conjecture with an ingenious but elementary two-page argument about the combinatorics of points on cubes.
From Quanta Magazine
View Full Article
No entries found