Amazing breakthrough in theory of computation

I learned from a colleague at JD.com that a professor Huang Hao from Emory math department made breakthrough just weeks ago in the following conjecture of Gotsman and Linial:

Given any induced subgraph $G$ of the hypercube graph $Q_n$, with $V(G) \geq 2^{n-1} + 1$, its maximum degree is at least $\sqrt{n}$. This by itself is already a big deal since the previous best result by famous people like Fan Chung was on the order of $\log(n)$, and presumably not obvious either.

Since the prof is Chinese, it was well advertised in the Chinese blogging community, though not to the extent of Yitang Zhang’s prime gap result.

The connection to other areas of complexity theory is even more remarkable, and well-exposed in the author’s original paper. In fact, I found that the subsequent advertising blogs by other mathematicians and journalists to be largely not adding much expository value.

A notion of complexity is given by the so-called sensitivity $s$. For a boolean function $f: F_2^n \to F_2^1$, where $F_2 := \{0, 1\}$ viewed as a set, the sensitivity function is defined by $s(f, x) := |\{i \in [n]: f(x^{\{i\}}) \neq f(x)\}|$, where $x^{\{i\}}$ stands for the binary vector $x$ with the $i$-th coordinate flipped. In other words, point-wise sensitivity is the number of ways the function $f$ can be perturbed by a single coordinate, or more metaphorically, the co-dimension of its null tangent space at $x$. Global sensitivity of $f$ is simply $s(f) := \max \{s(f, x): x \in F_2^n\}$. This is a natural measure of complexity of $f$ since if $f$ is constant, sensitivity is clearly $0$. But maybe it’s not fundamental enough to let us tackle P versus NP because for a simple function like the parity function $f(x) := |\{i \in [n]: x_i = 0\}| % 2$, $s(f) = n$ already achieves maximum sensitivity.

Now the connection between sensitivity and maximum degree is proved by Gotsman and Linial in a quarter-page proof, so I encourage everyone to read it. But here is my digested version:

The following two statements are equivalent:

1. The max degree of $G$ and the induced subgraph on $Q_n \setminus G$ is bounded below by $h(n)$, provided $|V(G)| \neq 2^{n-1}$.
2. The sensitivity of a boolean function $f: F_2^n \to F_2$ with $d(f) = n$ satisfies $s(f) >= h(d(f))$ where $d(f)$ is the degree of $f$, viewed as a polynomial. More precisely, $\max \{|\{i \in [n]: x_i = 1\}|: f(x) = 1\}$.

To see the equivalence, simply consider the indicator function $g$ of $V(G)$ with domain $F_2^n$, multiplied by the parity function $p$. The degree of $gp$ at $x \in Q_n$ is clearly related to its sensitivity at $x \in F_2^n$. Indeed the parity makes so that neighbors in the original graph $G$ change the function value.

The requirement of $|V(G)| \neq 2^{n-1}$ corresponds to $\mathbb{E} g \neq 0$, which in turn corresponds to $d(f) = n$. The rest should be pretty straightforward.

Statement 2 can be equivalently relaxed to the case where $d(f) < n$. The reason, as pointed out to me by Gil Kalai, is that given a function of degree $d < n$, there is a monomial $x_1 \ldots x_d$ of exactly $d$ variables. Let $g(x_1, \ldots, x_d) = f(x_1, \ldots, x_d, 0, \ldots 0)$. Then $g$ has degree $d$ and sensitivity less than or equal to that of $f$. But $g$ has full degree (equal to the dimension of its domain), so 2 applies. And we get $s(f) \geq s(g) \geq h(d(g)) = h(d) = h(d(f)).$

I will devote another post for Huang’s actual proof. 