Worked solution: Huang's signed hypercube adjacency matrix proof of the sensitivity conjecture (2019)

Step 7 of 7: Closing the loop: the sensitivity conjecture is settled

In plain words

One more ingredient, proved earlier by other authors, finishes the job: block sensitivity $bs(f)$ is never much bigger than $\deg(f)$ . Chaining that fact together with Huang's new bound $s(f) \ge \sqrt{\deg(f)}$ produces a direct polynomial link between $bs(f)$ and $s(f)$ , exactly what Nisan and Szegedy had asked for in 1992.

bs(f) \le s(f)^4

Detailed analysis

Nisan and Szegedy (1992) had already shown $bs(f) \le \deg(f)^2$ up to a constant factor, later sharpened by Tal (2013) to exactly $bs(f) \le \deg(f)^2$ . Squaring Theorem 1.4 from Step 6 gives $\deg(f) \le s(f)^2$ , and substituting into Tal's bound gives $bs(f) \le s(f)^4$ for every Boolean function $f$ . This is precisely the polynomial relationship the Sensitivity Conjecture asked for (with the explicit constant $C=4$ ), so Huang's short spectral argument -- built from nothing more than one clever matrix, one classical eigenvalue-interlacing theorem, and one elementary row-sum estimate -- closes a problem that had resisted attack for close to thirty years.

Terms in this step

Block sensitivity $bs(f)$: A relaxation of sensitivity: the largest number of pairwise disjoint blocks of coordinates that can each individually be flipped to change the value of $f$ at some input.