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 a $2^n \times 2^n$ Hermitian unitary matrix $U_n$ ($= A_n/\sqrt n$, where $A_n$ is from Huang's paper) such that, for some enumeration $v_1,v_2,\ldots,v_{2^n}$ of the vertices of the [hypercube graph](https://en.wikipedia.org/wiki/Hypercube_graph) $Q_n$, we have that the $(i,j)$th entry of $U_n$ is $0$ unless $(v_i,v_j)$ is an edge of $Q_n$. (Huang's matrix is actually symmetric but the more general Hermitian case also handles the skew-symmetric Klee-Minty matrix described by Knuth in a footnote.)

We can view this Hermitian unitary matrix as a (complex-valued) weighting on the edges of the graph. In the general case, for a graph $G = (V,E)$, lets say that a weighting $w:E \to \mathbb{C}$ is Hermitian unitary if the matrix $U$ whose entries are $$u_{ij} = \begin{cases} w(v_i,v_j) & \text{if $(v_i,v_j) \in E$,} \\ 0 & \text{otherwise,} \end{cases}$$ is Hermitian unitary for any (and hence all) enumerations $v_1,v_2,\ldots,v_n$ of $V$.

In other words:

* Hermitian: $w(u,v) = \overline{w(v,u)}$ for all $(u,v) \in E$
* Unitary: for all $u,v \in V$, $$\sum_{\substack{t \in V \\ (u,t),(v,t) \in E}} w(u,t)\overline{w(v,t)} = \sum_{\substack{t \in V \\ (u,t),(t,v) \in E}} w(u,t)w(t,v) = \begin{cases} 1 & \text{if $u = v$,} \\ 0 & \text{otherwise.} \end{cases}$$

**Theorem.** Suppose $G = (V,E)$ has a Hermitian unitary weighting $w$. 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 weightings as above? Is this rare, common, neither? 

* 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 a Hermitian unitary 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 bridge these gaps.

---

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.$