Favorite Theorems: Sensitivity

February Edition

Our next favorite theorem gave a relatively simple proof of the sensitivity conjecture, a long-standing problem of Boolean functions.

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

by Hao Huang

Consider the following measures of Boolean functions \(f:\{0,1\}^n\rightarrow\{0,1\}\) on an input x

• Decision tree complexity: How many bits of an input do you need to query to determine \(f(x)\)
• Probabilistic decision tree complexity
• Quantum decision tree complexity
• Certificate complexity: Least number of bits that forces the function
• Polynomial degree complexity: What is the smallest degree of a polynomial p over the reals such that \(p(x_1,\ldots,x_n)=f(x_1,\ldots,x_n)\) for \(x\in\{0,1\}^n\). 
• Approximate polynomial degree complexity: Same as above but only require \(|p(x_1,\ldots,x_n)-f(x_1,\ldots,x_n)|\leq 1/3\).
• Sensitivity: Over all x, what is the maximum number of i such that if  x' is x with the ith bit flipped then \(f(x)\neq f(x')\).
• Block sensitivity: Same as sensitivity but you can flip disjoint blocks of bits.

Based mostly on the 1994 classic paper by Nisan and Szegedy, all of the above measures, except for sensitivity, are polynomially related, in particularly if say f has polylogarithmic decision-tree complexity then they all have polylogarithmic complexity. The sensitivity conjecture states that sensitivity is polynomially related to the rest. I wrote about the conjecture in 2017 and a combinatorial game that, if solved the right way, could settle the conjecture.

Twenty-five years later Huang settled the conjecture in the positive, and now all the above measures are known to be polynomially-related. His proof uses eigenvalues of some cleverly constructed matrices. 

So what's left? The game remains open. Also whether the rational degree is polynomially-related to all the above. But sensitivity was the big one!