Mathematician Solves Near-30Yr-Old Computer Science Problem in Two Pages

Hao Huang, a mathematician at Emory University in Atlanta, Georgia, has solved the computer science sensitivity conjecture, which is a nearly 30-year-old problem.

The conjecture is about the structure of the fundamental building blocks of computer circuits. “This conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science,” said Scott Aaronson, University of Texas, Austin, U.S.

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.

Here is how the “sensitivity” conjecture emerged and became a lasting nightmare to computer science.

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.

Each measure provides a unique window into the structure of the Boolean function. Yet computer scientists have found that almost all these measures fit into a unified framework, such that the value of any one of them is a rough gauge for the value of the others. However, only one complexity measure didn’t seem to fit in; and that was sensitivity.

In the early 1990s, Noam Nisan of the Hebrew University of Jerusalem and Mario Szegedy, now of Rutgers University, conjectured that sensitivity does indeed fit into this unified framework. But no one could prove it.

He Solved the So-Called Sensitivity of a Boolean Function

About 30 years later, the proof of the sensitivity conjecture became a reality, and not just proven but amazingly solved in just two pages by Hao Huang, which he presented last month at the International Conference on Random Structures and Algorithms, Zurich, Switzerland.

Huang employed a 200-year-old piece of mathematics called the Cauchy interlace theorem, which relates a matrix’s eigenvalues to those of a submatrix. This is potentially the perfect tool to study the relationship between a cube and a subset of its corners.

“I’ve been attacking this problem off and on since 2012. But the key idea emerged for me just about a week ago. I finally identified the right tool to solve it,” said Huang.

This sensitivity conjecture which has stumped many of the most prominent computer scientists over the years, got its new proof and surprisingly, so simple that one researcher summed it up in a single tweet.

“I hope this method might also have some potential to be applied to other combinatorial and complexity problems important to computer science,” Huang adds.