Degree and Sensitivity: Tails of Two Distributions

Parikshit Gopalan, Rocco A. Servedio, Avi Wigderson

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:

  1. 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.
  2. Moments via Random Restrictions: Sampling a random restriction leaving $k$ live variables ($\rho \leftarrow \mathcal{R}_{k,n}$) allows reinterpreting moments:
  3. The $k$-th sensitivity moment relates to the probability that a restricted function $f_\rho$ achieves full sensitivity.
  4. The $k$-th Fourier moment relates to the probability that $f_\rho$ achieves full degree.
  5. Tree Sensitivity and Proper Walks: To relax sensitivity, the authors introduce:
  6. Tree sensitivity ($ts(f)$): the size of the largest tree of sensitive edges where every edge corresponds to a distinct coordinate direction.
  7. Proper walks: paths in the hypercube where the first time a coordinate direction is flipped, it traverses a sensitive edge.
  8. 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

Abstract

The sensitivity of a Boolean function f is the maximum, over all inputs x, of the number of sensitive coordinates of x (namely the number of Hamming neighbors of x with different f-value). The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-s Boolean function can be computed by a polynomial over the reals of degree s^{O(1)}. The best known upper bounds on degree, however, are exponential rather than polynomial in s. Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be eps-approximated (in l_2) by a polynomial whose degree is s * polylog(1/eps). This is the first improvement on the folklore bound of s/eps. We prove this via a new "switching lemma for low-sensitivity functions" which establishes that a random restriction of a low-sensitivity function is very likely to have low decision tree depth. This is analogous to the well-known switching lemma for AC^0 circuits. Our proof analyzes the combinatorial structure of the graph G_f of sensitive edges of a Boolean function f. Understanding the structure of this graph is of independent interest as a means of understanding Boolean functions. We propose several new complexity measures for Boolean functions based on this graph, including tree sensitivity and component dimension, which may be viewed as relaxations of worst-case sensitivity, and we introduce some new techniques, such as proper walks and shifting, to analyze these measures. We use these notions to show that the graph of a function of full degree must be sufficiently complex, and that random restrictions of low-sensitivity functions are unlikely to lead to such complex graphs. We postulate a robust analogue of the sensitivity conjecture: if most inputs to a Boolean function f have low sensitivity, then most of the Fourier mass of f is concentrated on small subsets. We prove a lower bound on tree sensitivity in terms of decision tree depth, and show that a polynomial strengthening of this lower bound implies the robust conjecture. We feel that studying the graph G_f is interesting in its own right, and we hope that some of the notions and techniques we introduce in this work will be of use in its further study.
BibTeX
@inproceedings{gopalan2016degree,
  author = {Parikshit Gopalan and Rocco A. Servedio and Avi Wigderson},
  title = {{Degree and Sensitivity: Tails of Two Distributions}},
  booktitle = {Computational Complexity Conference},
  year = {2016},
  url = {https://openreview.net/forum?id=xUOdnHlV4q},
}

Loading related content...

Figure