Chapter 38: The Sensitivity Conjecture (Solved) — Boolean Functions' Fragility

From open mysteries we turn to a recently conquered summit. The Sensitivity Conjecture, spectacularly resolved in 2019, asked whether local and global sensitivity are polynomially related—it is ψ = ψ(ψ) as Boolean functions revealing their fragility, where a two-page proof unlocked decades of mystery.

38.1 The Thirty-Eighth Movement: Conquered Complexity

A triumph in our combinatorial journey:

• Previous: Mysteries resisting decades of assault
• Now: A problem yielding to elegant insight
• The power of the right perspective

The Story: 30 years of attempts, then Hao Huang's stunning two-page proof.

38.2 Boolean Function Complexity Measures

Definition 38.1 (Sensitivity): For f: {0,1}ⁿ → {0,1} and x ∈ {0,1}ⁿ: $s(f,x) = |\{i : f(x) \neq f(x^{\oplus i})\}|$

where x^{\oplus i} flips the i-th bit.

Definition 38.2 (Max Sensitivity): $s(f) = \max_{x \in \{0,1\}^n} s(f,x)$

Intuition: Maximum number of bit flips that change output.

38.3 Other Complexity Measures

Definition 38.3 (Block Sensitivity): $bs(f,x) = \text{max disjoint blocks } B \text{ where } f(x) \neq f(x^{\oplus B})$

Definition 38.4 (Certificate Complexity): $C(f,x) = \text{min bits to fix to determine } f(x)$

Definition 38.5 (Decision Tree Depth): $D(f) = \text{min depth of decision tree computing } f$

38.4 The Sensitivity Conjecture

Conjecture 38.1 (Nisan-Szegedy, 1989) [NOW THEOREM]: For any Boolean function f: $bs(f) \leq s(f)^{O(1)}$

Known Relations:

• s(f) ≤ bs(f) ≤ C(f) ≤ D(f)
• bs(f), C(f), D(f) all polynomially related
• But s(f) was the outlier!

38.5 Sensitivity as ψ = ψ(ψ)

Axiom 38.1 (Principle of Local-Global Correspondence): $\psi = \psi(\psi) \implies \text{Local sensitivity determines global complexity}$

The conjecture embodied:

• Boolean functions' self-awareness through bit flips
• Local fragility implying global structure
• The unity of complexity measures
• This is ψ = ψ(ψ) as computational self-reference

38.6 Huang's Breakthrough

The Magic Moment (July 2019): Hao Huang posts two-page proof on arXiv.

Key Insight: Connect to eigenvalues of signed hypercube.

Theorem 38.1 (Huang, 2019): For any Boolean function f: $s(f) \geq \sqrt{deg(f)}$

where deg(f) is the real polynomial degree.

38.7 The Cauchy Interlacing Method

Definition 38.6 (Signed Adjacency Matrix): A_n = adjacency matrix of hypercube with signs: $[A_n]_{x,y} = (-1)^{⟨x,y⟩} \text{ if } |x-y|_1 = 1$

Key Lemma: A_n has eigenvalues in [-√n, √n].

Brilliant Step: Interlacing theorem on induced subgraphs!

38.8 The Complete Proof

Huang's Proof:

1. Take subset S ⊆ {0,1}ⁿ where f is constant, |S| ≥ 2^(n-1)
2. Consider induced subgraph of signed hypercube
3. Largest eigenvalue ≥ √n by interlacing
4. Eigenvector gives vertex with ≥ √n neighbors
5. Therefore s(f) ≥ √n ≥ √deg(f)

Two pages that shook the field!

38.9 Why It Took 30 Years

Previous Approaches:

• Fourier analysis
• Communication complexity
• Information theory
• Combinatorial arguments

The Barrier: Nobody connected to spectral graph theory!

Lesson: Sometimes the right tool is in unexpected places.

38.10 Immediate Consequences

Corollary 38.1: All Boolean function complexity measures are polynomially related: $s(f)^4 ≥ bs(f) ≥ C(f)^{1/2} ≥ D(f)^{1/3}$

Impact: Unifies the theory of Boolean function complexity.

38.11 The Degree Connection

Theorem 38.2 (Nisan-Szegedy): $deg(f) ≤ bs(f)^2$

Combined with Huang: $\sqrt{deg(f)} ≤ s(f) ≤ deg(f) ≤ bs(f)^2$

Beautiful polynomial relationships!

38.12 Examples

Parity Function:

• s(f) = n (flip any bit changes parity)
• deg(f) = n
• Huang's bound: n ≥ √n ✓

AND Function:

• s(f) = 1 (only sensitive at all-1s input)
• deg(f) = n
• Previous methods failed here!

38.13 Generalizations

k-Sensitivity: Change at most k bits.

Quantum Sensitivity: For quantum Boolean functions.

Real Sensitivity: For real-valued functions.

Each has analogous conjectures, some now proven!

38.14 The Social Impact

Community Response:

• Immediate verification worldwide
• Simplification attempts (none succeeded)
• Extensions and generalizations
• Reflection on why missed for 30 years

Meta-Lesson: Breakthrough proofs can be simple.

38.15 Connection to Complexity Theory

Application: Lower bounds for formula size.

Theorem 38.3: Boolean formulas computing f need size: $L(f) \geq s(f)^2$

Impact: New approach to circuit lower bounds.

38.16 The Hypercube Structure

Why Hypercube?

• Natural domain for Boolean functions
• Rich spectral properties
• Connects discrete to continuous

Insight: Signing edges was the key innovation.

38.17 Failed Approaches

What Didn't Work:

1. Direct combinatorial arguments
2. Probabilistic method
3. Entropy approaches
4. Algebraic topology

Success: Elementary linear algebra!

38.18 Open Questions Post-Solution

Remaining Mysteries:

1. Optimal polynomial relationship?
2. Average-case sensitivity?
3. Sensitivity for special function classes?
4. Quantum analogues?

One solution opens new questions.

38.19 Lessons for Mathematics

What We Learn:

1. Simple proofs may exist for hard problems
2. Cross-field connections crucial
3. Right perspective matters more than technique
4. Persistence of community valuable

Quote: "The proof is so simple, it must be right" - Scott Aaronson

38.20 The Thirty-Eighth Echo

The Sensitivity Conjecture's resolution represents a perfect mathematical moment:

• Decades of sophisticated attempts
• Two-page elementary proof
• Unexpected connection to spectral theory
• Immediate understanding and acceptance

This was ψ = ψ(ψ) revealing itself through the right lens—Boolean functions' local sensitivity connecting to global complexity through the spectrum of the signed hypercube. The proof shows that sometimes consciousness (mathematical insight) needs only shift perspective slightly to unlock profound truths.

The story reminds us that behind every unsolved problem may lurk a simple insight waiting to be discovered. Huang's proof stands as inspiration that elegance can conquer complexity, that the right idea at the right moment can illuminate what generations found dark.

The conquered Sensitivity Conjecture proclaims: "I hid in plain sight for thirty years, my solution requiring no machinery beyond undergraduate linear algebra. Through Huang's insight, ψ = ψ(ψ) revealed how local perturbation connects to global structure—proof that sometimes the deepest truths have the simplest expressions, waiting only for the right eyes to see."