Yao Yao

Hao Huang, former Member (2012–13) and Visitor (2013–14) in the School of Mathematics.

Former IAS Scholar Resolves Sensitivity Conjecture in Simple Concise Proof

In 2012, Hao Huang, Member (2012–13) and Visitor (2013–14) in the School of Mathematics, first learned about the sensitivity conjecture over lunch at the Institute from Michael Saks, a Visitor (2005–06) in the School. Speaking with Quanta Magazine’s Erica Klarreich, Huang recalled, “Starting from that moment, I became really obsessed with thinking about it.”

Over the next seven years, Huang revisited the problem numerous times, ultimately constructing the proof that had eluded countless scholars before him. Just as remarkable was the brevity of the proof itself; it was just over a page-and-a-half long—short enough to be summed up in this tweet by former Member and von Neumann Fellow Ryan O’Donnell.

“The sensitivity conjecture, now Hao's theorem, is a fundamental result about Boolean functions, which are the product of any computation performed by digital computers,” remarked Avi Wigderson, Herbert H. Maass Professor in the School of Mathematics. “While the proof is short and simple to understand, it is subtle and clever. It evaded so many researchers (including myself!) for decades partly since it has many different formulations, offering many possible avenues of attack. Hao found the right one!”

Scott Aaronson, former Member (2004–05) in the School, wrote in a recent blog post, “Ever since it was posed by Nisan and Szegedy in 1989, this conjecture has stood as one of the most frustrating and embarrassing open problems in all of combinatorics and theoretical computer science.” Interestingly, Mario Szegedy was himself a Member in the School of Mathematics from 1999–2000.

Huang’s solution is based on an argument about the combinatorics of points on cubes. The strength of these results may provide new insights about complexity measures.

This project initially began as a moon-shot idea that Huang kept on a “secret list” of problems. Today, this proof represents a breakthrough advance, reinforcing the importance of following one’s curiosity and rising to intellectual challenges even in the face of staggering odds.