Tools and Sensitivity

Gödel’s Lost Letter and P=NP 2019-08-20

Cutting right through a 30-year-old conjecture

Cropped from Emory homepage

Hao Huang is a mathematician and computer scientist at Emory University. Last week he released a paper of only six pages that solves the Boolean Sensitivity Conjecture, which goes back at least to a 1992 paper by Noam Nisan and Mario Szegedy.

Today we discuss his brilliant proof and what it means for sensitivity of the tools one employs.

Several of our blogging friends have covered this news in posts already, and Ryan O’Donnell even summarized the proof in one tweet. Scott Aaronson’s thread includes a comment by Huang on how he came by his proof.

We will try to draw implications for the related matter of how you might come by proofs of other conjectures. We have previously discussed the possibility of overlooking short solutions to major problems. Here we will discuss how to find them.

A Graph Puzzle

To get a flavor of what Huang proved, consider the graph of an ordinary cube:

The question is, can you color 5 vertices red so that no red node has 3 red neighbors? Your first impulse might be to color 4 nodes red according to parity so that none has a red neighbor, per below left:

But then any 5th node will have 3 red neighbors. Another “greedy” idea is to pack a subgraph of the allowed degree 2 into half the cube, as at right. Any 5th node will again create a degree-3 vertex in the subgraph induced by the red nodes.

The answer is that actually one can pack 6 nodes that induce a simple cycle:

Now let’s up the dimension by one—that is, take ${n = 4}$ and ${N = 2^n = 16}$ . How many nodes can we color red and keep the induced degree 2?

Again the parity trick gives us degree 0 with 8 nodes, but then we can’t add a 9th. We can greedily try to pack the outer cube with our 6-node solution, but then—perhaps surprisingly—we can add only 2 more red nodes from the inner cube. So we can only do 5 from the outer cube. We can get 9 overall by:

The fact that one red node is isolated seems to give room to improve, but there is no way to make 10.

The Theorem

The calculations have left an interesting jump from degree 0 with eight red nodes and degree 2 with nine. How about degree 1? Can we do that with 9 nodes? We can pack four disjoint edges but then there is nowhere to stick an isolated node.

So for 9 nodes, which is ${\frac{N}{2} + 1}$ , the best we can do is degree 2, which is ${\sqrt{n}}$ . This is what Huang proved:

Theorem 1 Every subgraph induced by ${\frac{N}{2} + 1}$ nodes of the ${n}$ -dimensional hypercube graph has a node of degree at least ${\sqrt{n}}$ .

This is completely tight. When ${n}$ is a perfect square there is a way to achieve ${\sqrt{n}}$ as the maximum degree (shown here). Otherwise the least integer above ${\sqrt{n}}$ is best. Thus every subgraph of the ${5}$ -cube induced by 17 nodes has a node with three neighbors, but you can go as high as 257 nodes in the ${9}$ -cube while keeping the maximum degree to 3.

We will mention the relation to Boolean sensitivity only briefly. The nodes of the ${n}$ -cube correspond to truth assignments in ${\{0,1\}^n}$ . Since every red node ${x}$ has ${n}$ neighbors in the cube but at most ${\sqrt{n}}$ red neighbors, the color function is highly sensitive to bitflips. But every flip also changes the parity of ${x}$ . Hence the exclusive-or of the color function with the parity function has low sensitivity.

But not too low: Huang proved it is at least ${\sqrt{n}}$ . That was enough to prove the conjecture. I’ve cut two sections on Boolean sensitivity from this post’s original draft—let’s just say the connection to the ${n}$ -cube and graph degree was known since this 1992 paper. Here we’ll focus on what it took to prove this theorem.

The Proof

From my undergrad days I’ve kept an interest in spectral graph theory. One of the basic facts is that the degree ${d(G)}$ of a graph ${G}$ is always at least as great as the largest eigenvalue ${\lambda}$ of its adjacency matrix ${A_G}$ . For a ${d}$ -regular graph they are equal. Huang’s first trick is to note that the classic proof of this also allows ${-1}$ values on edges:

Lemma 2 Let ${A}$ be a symmetric matrix obtained from ${A_G}$ by multiplying some entries by ${-1}$ and ${\lambda}$ any of its eigenvalues. Then ${d(G) \geq |\lambda|}$ .

Proof: Choose an eigenvector ${v}$ such that ${Av = \lambda v}$ and take an index ${i}$ that maximizes ${|v_i|}$ . Then

$\displaystyle |\lambda v_i| = |(A v)_i| = |\sum_j A_{i,j} v_j| \leq |\sum_j A_{i,j}| \cdot |v_i| \leq \sum_{(i,j) \in E(G)} |A_{i,j}|\cdot |v_i| \leq d(G)|v_i|.$

Dividing out ${|v_i|}$ gives the lemma. $\Box$

So now what we want to do is find conditions that force ${\lambda = \sqrt{n}}$ when ${G}$ is a ${m}$ -vertex subgraph of the ${n}$ -cube with ${m \geq \frac{N}{2} + 1}$ , where ${N = 2^n}$ . The trick that Huang realized is that he could do this by making ${A}$ sit inside a matrix ${A_N}$ with at least ${\frac{N}{2}}$ eigenvalues of ${+\sqrt{n}}$ .

To see how, form ${A_{N-1}}$ by knocking out the last row and column of ${A_N}$ . Since ${A_N}$ and ${A_{N-1}}$ are both real and symmetric, their eigenvalues are real, so we can order them ${\lambda_1,\dots,\lambda_N}$ and ${\mu_1,\dots,\mu_{N-1}}$ in nonincreasing order. The basic fact is that they always interlace:

$\displaystyle \lambda_1 \geq \mu_1 \geq \lambda_2 \geq \mu_2 \geq \lambda_3 \geq \cdots \geq \mu_{N-1} \geq \lambda_N.$

See this for a one-page proof. The neat point is that you can repeat this: if you get ${A''}$ by knocking out another row and corresponding column, and ${[\nu_i]}$ are its eigenvalues in order, then

$\displaystyle \mu_1 \geq \nu_1 \geq \mu_2 \geq \nu_2 \geq \mu_3 \cdots.$

It follows that ${\lambda_1 \geq \nu_1 \geq \lambda_3}$ . If you do this again, you get a matrix whose leading eigenvalue is still at least as big as ${\lambda_4}$ . Do it ${\frac{N}{2} - 1}$ times inside ${A_N}$ , and you’re still above ${\lambda_{N/2}(A_N)}$ , which we just said we will arrange to be ${+\sqrt{n}}$ . Thus if we knock out the ${\frac{N}{2} - 1}$ white nodes, we will get the graph on the red nodes with adjacency matrix ${A_m}$ and conclude:

$\displaystyle \lambda_1(A_N) \geq \lambda_1(A_m) \geq \lambda_{N/2}(A_N)$

Plugging into the lemma gives:

$\displaystyle d(G) \geq \lambda_1(A_m) \geq \lambda_{N/2}(A_N) = \sqrt{n}.$

(In fact, as also noted on Scott’s blog, this case of interlacing can be inferred from simpler reasoning—but our point is that the interlacing theorem was in Huang’s bag of tricks.)

Building the Matrix

Finally, how do we lay hands on ${A_N}$ ? We want a matrix of trace zero such that ${A_N^2 = nI}$ . Then all its eigenvalues are ${+\sqrt{n}}$ and ${-\sqrt{n}}$ . They come in equal numbers because they sum to the trace which is zero. So we will have ${N/2}$ eigenvalues of ${+\sqrt{n}}$ , as needed. And we would want ${A_N}$ to be the matrix of the ${n}$ -cube but that doesn’t work: each ${i,j}$ entry of its square counts all paths of length 2 from node ${i}$ to node ${j}$ and that number can be nonzero.

This is where the trick of putting ${-1}$ on edges comes in, and we can explain it in a way familiar from quantum. We arrange that every 4-cycle of the ${n}$ -cube has exactly one edge with ${-1}$ . Then the pairs of paths from one corner to the opposite corner will always cancel, leaving ${A^2_{i,j} = 0}$ whenever ${i \neq j}$ . And ${A^2_{i,j} = n}$ because there are ${n}$ ways to go out and come back along the same edge, always contributing ${1\cdot 1}$ or ${(-1)\cdot(-1) = 1}$ either way. Huang defines the needed labeling explicitly by the recursion:

$\displaystyle A_2 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix},\quad\text{and for } N > 2,\quad A_N = \begin{bmatrix} A_{N/2} & I \\ I & -A_{N/2} \end{bmatrix}.$

This puts a ${-}$ sign on exactly one-fourth of the entries in the needed way. OK, we changed Huang’s subscripts for consistency with “ ${A_N}$ ” above and also to note that the basis could be ${A_1 = [0]}$ . Anyway, he verifies ${A_N^2 = nI}$ directly by simple algebra and induction. That’s it—that’s the proof.

Why was it hard to spot? Dick and I believe it was the ${-1}$ trick. In the 1980s, I thought about ways to convert undirected graphs into directed ones by putting arrows on the edges, but not ${-1}$ signs. The chance of thinking of it maybe rises with knowing quantum ideas such as interference and amplification. Now we can see, OK, ${A_2}$ is the quantum NOT gate and the recursion treats signs in similar fashion to the recursion defining Hadamard matrices. The matrix ${\frac{1}{\sqrt{n}}A_N}$ is unitary, so it defines a quantum operator. This all goes to our main point about having tools at one’s command—the more tools, the better.

Open Problems

Huang’s theorem still leaves a gap between a quadratic lower bound and his 4th-power upper bound (my longer draft lays this out). Can this gap be closed? In discussing this, Huang notes that his spectral methods need not be confined to sub-matrices of the ${n}$ -cube, and our thoughts of involving quantum are similar. Can quantum tools improve the results even further?