Hao Huang, an assistant professor in the Department of Mathematics, was doubtful when he posted a six-page paper on his website claiming to prove a 27-year-old conjecture in theoretical computer science.
“I was not very sure whether the proof was true,” Huang said. “Whenever I thought I found a proof, 99 percent of the time it was wrong.”
Despite his apprehension, Huang’s solution was quickly met with widespread validation and praise from experts in mathematics and computer science.
Huang’s work proved the Sensitivity Conjecture, a problem first posed in 1992 by computer scientists Noam Nisan at the Hebrew University of Jerusalem and Mario Szegedy at Rutgers University (N.J.).
The conjecture deals with the relationships between the complexity of Boolean functions, which are functions that take values from a two-element set. An example of a two-element set could be any pair such as 0 and 1, or true and false. Boolean functions can have varying levels of complexity. The “sensitivity” measure of a Boolean function determines how changing one input bit affects the output.
The decades-old problem “has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science,” wrote Scott Aaronson, professor of computer science at the University of Texas at Austin, in a blog post about Huang’s proof.
“All the tools that I used [have existed] for a long time, maybe for 20 to 30 years,” Huang said. “But it’s difficult to put them together. [All I did] was put them together.”
Of the paper’s six pages, only one-and-a-half were needed to prove the conjecture, a brevity nearly unheard of in modern mathematical proofs. Carnegie Mellon University (Pa.) Professor of Computer Science Ryan O’Donnell managed to summarize Huang’s entire argument in a single tweet.
In an interview with the Wheel, Aaronson called the solution one of the “most exciting results of the decade within computer science.”
Aaronson added that the simplicity of the proof makes it widely applicable to other math problems and viable for teaching in even undergraduate courses.
Huang said that the proof’s brevity made it easier to verify. Typically, experts may take months or years to reach consensus on longer mathematical proofs.
“For a short proof like this, an expert just needs 10 minutes to see if it is correct,” Huang said. “For 100-page proofs, it can take people months or years to understand them.”
Cracking the Problem
In 2012, while working at the Institute for Advanced Study (N.J.), Huang learned about the problem from Rutgers University Chair of Mathematics Michael Saks. Huang has tackled the problem on and off ever since.
Over time, as research continued to uncover different methods of measuring the complexity of a Boolean function, the measures were shown to be related to each other polynomially, or by coefficients and positive exponents.
“Knowing [one complexity measure] gives you a handle on the others,” Aaronson said. “[Each measure] is bounded by a product of other measures.”
Previously, mathematicians had shown a polynomial relationship between all complexity measures of Boolean functions except for sensitivity.
Nisan and Szegedy believed that block sensitivity — a different complexity measure proven to be related to the other measures — and sensitivity were polynomially related. If Huang could show that they were, he would prove that sensitivity is related to all the measures, solving the conjecture.
Computer scientists Craig Gotsman and Nati Linial also found in 1992 that proving a different problem in combinatorics, the Gotsman-Linial Conjecture, would prove the Sensitivity Conjecture.
Converting the problem from a computer science one to a mathematical one involved visualizing each input bit as a point on a cube. Huang conceptualized this mathematical problem using matrices and represented adjacent and nonadjacent points on a matrix with 1 and 0, respectively.
Although he solved the combinatorial problem, he only proved the relationship between block sensitivity and sensitivity to the fourth power.
Huang added that researchers believe that the relationship can be proved to a lower power, but he is unsure how much time he will devote to the subject.
Following the publication of his paper, he received emails of congratulations from other researchers who also proposed short proofs to well known mathematical problems, including the Goldbach Conjecture.
“I got a lot of emails, some of them congrats. Some of them sent me papers that had this type of result,” Huang said. “[Their] feeling is that if some guy did a one-and-a-half page proof, and he got recognized by the community, maybe he can recognize their proof.”
