Very recently, Hao Huang proved the Sensitivity Conjecture, which had been open for 30 years or so. Huang's proof is surprisingly short and easy. Here is [Huang's preprint](http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf), a [discussion on Scott Aaronson's blog](https://www.scottaaronson.com/blog/?p=4229), and a one-page streamlined [proof by Don Knuth](https://www.cs.stanford.edu/~knuth/papers/huang.pdf).

Huang's proof relies on the existence of an edge weighing $w$ on the [hypercube graph](https://en.wikipedia.org/wiki/Hypercube_graph) $Q_n$. Where if one forms the $2^n\times2^n$ matrix $U_n$ ($= A_n/\sqrt n$ from Huang's paper) where the $(i,j)$-th entry of $U_n$ is $w(v_i,v_j)$ for some enumeration $v_1,\ldots,v_{2^n}$ of the vertices of $Q_n$, then $U_n$ is both unitary and Hermitian. (Huang's matrix is actually symmetric but the more general Hermitian case also covers the skew-symmetric Klee-Minty matrix described by Knuth in a footnote.)

It's easy to see that Huang's result holds for any graph $G=(V,E)$ with a weighting $w$ as described above:

**Theorem.** Suppose there is a weighting $w$ of the edges of the graph $G = (V,E)$ such that the matrix $U$ is both Hermitian and unitary, where the $(i,j)$-th entry of $U$ is $w(v_i,v_j)$ for some enumeration $v_1,v_2,\ldots,v_n$ of $V$. Then for every set $H \subseteq V$ with $|H| > n/2$, there is a $v \in H$ which is connected to at least $1/\Vert U\Vert_{\infty}$ vertices inside $H$, where $\|U\|_\infty$ is the maximum absolute value $|w(u,v)|$ ranging over edges $uv$ of $G$.

(In the case of Huang's proof, $U = \frac{1}{\sqrt{n}}A_n$ has all entries in $\{0,\pm1/\sqrt{n}\}$ and the result follows immediately. In the Klee-Minty case the entries of $U = \frac{i}{\sqrt n}\widehat{A}_n$ are all in $\{0,\pm i/\sqrt{n}\},$ using notation from Knuth.)

It is surprising that this was not noticed for 30 years until Huang put the pieces together. (The [Klee-Minty cube](https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube) has been around since 1973!) Why this was never noticed is interesting but, even after this fact, there are still some follow-up questions:

* Which graphs have Hermitian unitary edge weights as above?

* Is there an algorithm to build such edge weights, given that one exists?

* How hard is it to compute the minimum value of $\Vert U \Vert_\infty,$ given that such a weighting exists? 

And probably many more related questions... Since there is strong evidence that connections between existing literature are missing, this is an opportune time to fix these lacunas.

---

Since the theorem above is somewhat more general than what Huang proved, here is a quick proof:

Since $U$ is Hermitian, it is unitarily diagonalizable with real eigenvalues. Since $U$ is unitary, the only possible eigenvalues are $\pm1.$ One of the two eigenspaces $E_{\pm} = \{ x : Ux = \pm x \}$ has dimension at least $n/2.$ Replacing $U$ by $-U$ if necessary, we may suppose $\dim E_{+} \geq n/2.$ Since $|V - H| < n/2,$ we can find an eigenvector $x \in E_{+}$ such that $x_i = 0$ when $v_i \notin H.$ Scaling $x$ if necessary, we may assume that $\|x\|_\infty = 1$ and that there is a $j$ with $x_j = 1.$ Then
$$1 = |x_j| = \Big|\sum_{k=1}^n w(v_j,v_k)x_k\Big| \leq \sum_{k=1}^n |w(v_j,v_k)||x_k| \leq \Vert U\Vert_\infty |\{ k \mid w(v_j,v_k) \neq 0, x_k \neq 0\}|.$$
Now $v_j \in H$ since $x_j \neq 0$ and since $$\{ k \mid w(v_j,v_k) \neq 0, x_k \neq 0\} \subseteq \{ k \mid (v_j,v_k) \in E, v_k \in H \}$$ we see that $v_j$ is connected to at least $1/\Vert U \Vert_\infty$ vertices in $H.$