Emory mathematician to present a proof of the Sensitivity Conjecture

Emory mathematician Hao Huang says that the algebraic tool that he developed to tackle the problem "might also have some potential to be applied to other combinatorial and complexity problems important to computer science.”

The Sensitivity Conjecture has stood as one of the most important, and baffling, open problems in theoretical computer science for nearly three decades. It appears to have finally met its match through work by Hao Huang, an assistant professor of mathematics at Emory University.

Huang will present a proof of the Sensitivity Conjecture during the International Conference on Random Structures and Algorithms, set for Zurich, Switzerland, July 15 to 19.

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

Huang posted the proof on his home page and it soon generated buzz among mathematicians and computer scientists on social media, who have praised its remarkable conciseness and simplicity.

The Sensitivity Conjecture relates to boolean data, which maps information into a true-false, or 1-0 binary. Boolean functions play an important role in complexity theory, as well in the design of circuits and chips for digital computers.

“In mathematics, a boolean function is one of the most basic discrete subjects — just like numbers, graphs or geometric shapes,” Huang explains.

There are many complexity measures of a boolean function, and almost all of them — including the decision-tree complexity, the certificate complexity, the randomized query complexity and many others — are known to be polynomially related. However, there is one unknown case, the so-called sensitivity of a boolean function, which measures how sensitive the function is when changing one input at a time.

In 1994, mathematicians Noam Nisan and Mario Szegedy proposed the Sensitivity Conjecture concerning this unknown case.

“Their conjecture says the sensitivity of a boolean function is also polynomially related to the other measures,” Huang says. “If true, then it would cease to be an outlier and it would join the rest of them.”

Huang developed an algebraic method for proving the conjecture. “I hope this method might also have some potential to be applied to other combinatorial and complexity problems important to computer science,” he says.

The research was supported in part by the Simons Foundation.