Just want to write stuff. Something about me. Categories. Resources.

Sensitive Conjecture

On a Friday early morning (which was 2:00am), I couldn’t sleep due to having taken a short nap before that, so I picked up the phone and read whatever Google Chrome’s news feed suggested to me. The first feed was interesting enough to catch my attention: some computer science conjecture was now announced resolved… in 2 pages, and it was from Quanta Magazine. The full title is: “Decades-Old Computer Science Conjecture Solved in Two Pages.”

It is all due to Hao Huang, a mathematician from Emory University. He actually proved a stronger statement that provides a more qualitative aspect of the problem. The conjecture claims that sensitivity of a Boolean function \(f\) can be controlled by other complexity measures of \(f\).

More information can be found on Scott Aaronson’s blog. In the comment section, Huang is also kindly enough to detail the span of almost 7 years during which he came up with the solution.

The proof is indeed understandable with some basic knowledge of combinatorics and that is why it is impressive to be contained in just one and a half pages. One can say, the proof is taken from the book.