The
blogosphere is
blowing up over Hao Huang's just
posted proof of the sensitivity conjecture, what was one of the more
frustrating open questions in complexity. Huang, an assistant professor in the math department at Emory, settled an open question about the hypercube. The hypercube is a graph on N=2
n vertices where each vertex corresponds to an n-bit string and their are edges between vertices corresponding to strings that differ in a single bit. Think of the set of the strings of odd parity, N/2 vertices with no edges between them. Add any other vertex and it would have n neighbors. Huang showed that no matter how you placed those N/2+1 vertices in the hypercube, some vertex will have at least n
1/2 neighbors. By an
old result of Gotsman and Linial, Huang's theorem implies the sensitivity conjecture. I won't go through the shockingly simple proof, the
paper is well written, or you can read the blogs I linked to above or even just Ryan O'Donnell's
tweet. I have nothing more to say than wow, just wow.
The blogosphere is blowing up over Hao Huang's just posted proof of the sensitivity conjecture, what was one of the more frustrating open questions in complexity. Huang, an assistant professor in the math department at Emory, settled an open question about the hypercube. The hypercube is a graph on N=2n vertices where each vertex corresponds to an n-bit string and their are edges between vertices corresponding to strings that differ in a single bit. Think of the set of the strings of odd parity, N/2 vertices with no edges between them. Add any other vertex and it would have n neighbors. Huang showed that no matter how you placed those N/2+1 vertices in the hypercube, some vertex will have at least n1/2 neighbors. By an old result of Gotsman and Linial, Huang's theorem implies the sensitivity conjecture. I won't go through the shockingly simple proof, the paper is well written, or you can read the blogs I linked to above or even just Ryan O'Donnell's tweet. I have nothing more to say than wow, just wow.