TL;DR
This paper proves an approximate version of the celebrated Sensitivity Conjecture: any Boolean function with maximum sensitivity $s$ can be $\epsilon$-approximated (in $L_2$) by a real polynomial of degree $O(s \cdot \log^3(1/\epsilon))$. To achieve this exponential improvement over the folklore $O(s/\epsilon)$ bound, the authors develop a novel "switching lemma for low-sensitivity functions" based on the combinatorial structure of sensitive edges in the hypercube.
What Problem Does This Paper Address?
In theoretical computer science, understanding the relationship between different complexity measures of Boolean functions $f: \{0,1\}^n \to \{\pm 1\}$ is a central theme. While measures like block sensitivity, certificate complexity, and decision tree depth are known to be polynomially related to real polynomial degree $\deg(f)$, sensitivity $s(f)$—the maximum number of Hamming neighbors of an input that flip the function's output—notoriously resisted inclusion. The long-standing Sensitivity Conjecture posited that $\deg(f) \le \text{poly}(s(f))$.
While the exact conjecture remained open when this paper was written, the authors asked a natural relaxation: Can low-sensitivity functions at least be approximated well by low-degree polynomials? Prior to this work, the best known bound was the folklore $O(s/\epsilon)$ degree required for an $\epsilon$-approximation in $L_2$, derived simply from average sensitivity and Markov's inequality.
The paper also explores a broader, distributional question: if most inputs to a function have low sensitivity (rather than just worst-case inputs), is the function's Fourier spectrum concentrated on low-degree coefficients?
Methods
The authors introduce a framework linking random restrictions, Fourier analysis, and structural graph theory on the hypercube:
- The Sensitivity Graph ($G_f$): They analyze $G_f = (\{0,1\}^n, E)$, the subgraph of the hypercube containing only edges whose endpoints have different function values.
- Moments via Random Restrictions: Sampling a random restriction leaving $k$ live variables ($\rho \leftarrow \mathcal{R}_{k,n}$) allows reinterpreting moments:
- The $k$-th sensitivity moment relates to the probability that a restricted function $f_\rho$ achieves full sensitivity.
- The $k$-th Fourier moment relates to the probability that $f_\rho$ achieves full degree.
- Tree Sensitivity and Proper Walks: To relax sensitivity, the authors introduce:
- Tree sensitivity ($ts(f)$): the size of the largest tree of sensitive edges where every edge corresponds to a distinct coordinate direction.
- Proper walks: paths in the hypercube where the first time a coordinate direction is flipped, it traverses a sensitive edge.
- Switching Lemma for Low-Sensitivity Functions: The authors prove that if a function has full decision tree depth ($dt(f) = n$), it must contain a short proper walk (length at most $3n$). Using this structural result, they show that under a random restriction, low-sensitivity functions are overwhelmingly unlikely to maintain high decision tree depth.
Datasets
Not discussed in the paper (this is a purely theoretical paper; no experimental datasets or benchmarks were used).
Key Insights and Ideas
- Bridging Sensitivity and Decision Trees via Walks: A crucial conceptual leap is showing that $dt(f) = n$ forces the existence of an $n$-dimensional proper walk of length $\le 3n$. This bypasses previous bottlenecks and yields an analogue of Håstad’s Switching Lemma for sensitivity without relying on DNF representations.
- The "Orchard" Structure: Using a shifting technique along insensitive directions, the authors show that maximal sensitive trees must appear in highly symmetric families called orchards. Because any two orchards must share edge coordinates, they prove that $ts(f) \ge \sqrt{2 \, dt(f)} - 1$.
- Sidorenko's Theorem Connection: Using a result by Sidorenko on counting graph homomorphisms into trees (with a simplified random walk proof credited to Yuval Peres), the authors show that sensitivity moments directly control the distribution of tree sensitivity under random restrictions.
- Formulating the Robust Sensitivity Conjecture: The authors conjecture that for all integers $k \ge 1$, $\mathbb{E}[d^k] \le a_k \mathbb{E}[s^k]$, where $d$ is the Fourier degree distribution and $s$ is the sensitivity distribution. This posits that sensitivity bounds translate into Fourier concentration on average, not just in the worst case.
Key Results
-
Exponential Improvement in $L_2$ Approximation: For any Boolean function $f$ and error $\epsilon > 0$, there exists a polynomial $p$ of degree $$\deg(p) \le O\left(s(f) \cdot \left(\log \frac{1}{\epsilon}\right)^3\right)$$ such that $\mathbb{E}\left[(p(x) - f(x))^2\right] \le \epsilon$. This exponentially improves the error dependence compared to the folklore $O(s(f)/\epsilon)$.
-
Bounds on Higher Fourier Moments: The $k$-th influence/Fourier moment is upper bounded in terms of maximum sensitivity: $\mathbb{I}^k[f] \le (2k^3 s(f))^k$.
- Resolving the Robust Conjecture for Small $k$: The Robust Sensitivity Conjecture is proven true for $k = 3$ and $k = 4$ (with $k=1, 2$ being known classical identities).
Limitations and Future Work
- Dependence on Worst-Case Sensitivity: The main switching lemma and $L_2$ polynomial approximation rely on maximum sensitivity $s(f)$ rather than average or moment-based sensitivity, because an analogue of Sidorenko's theorem for proper walks remains unknown.
- Conjectured Tree Sensitivity Gap: The authors conjecture that $ts(f) \ge dt(f)$ (Conjecture 4.10). They only establish $ts(f) = \Omega(\sqrt{dt(f)})$; closing this quadratic gap would immediately prove the Robust Sensitivity Conjecture for all moments and yield an alternate combinatorial proof of the DNF switching lemma.
- Reverse Direction: The authors leave open whether the reverse inequality $\mathbb{E}[s^k] \le a'_k \mathbb{E}[d^k] + b'_k$ holds for all $k$.
Summary updated