Amazing breakthrough in theory of computation

I learned from a colleague at 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.

About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s