Degree and Sensitivity: tails of two distributions

Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson

Abstract

The sensitivity of a Boolean function $f$ is the maximum over all inputs $x$ of the number of sensitive coordinates of $x$. The well-known sensitivity conjecture of Nisan and Szegedy states that every sensitivity-$s$ Boolean function can be computed by a polynomial over the reals of degree $\text{poly}(s)$. 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 $\epsilon$-approximated (in $L_2$) by a polynomial whose degree is $O(s \log(1/\epsilon))$. This is the first improvement on the folklore bound of $s/\epsilon$. Further, we show that improving the bound to $O(s^c \log(1/\epsilon)^d)$ for any $d < 1$ and any $c > 0$ will imply the sensitivity conjecture. Thus our result is essentially the best one can hope for without proving the conjecture. 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, and present an approach towards proving this conjecture.

Introduction

In theoretical computer science, Boolean functions—functions mapping $n$ bits to $\pm 1$—are fundamental objects of study. Understanding their complexity often involves comparing different measures of "smoothness" or "simplicity." Two of the most prominent measures are:

  1. Sensitivity ($s$): A local measure. For a given input, how many single-bit flips change the output? The sensitivity of the function is the maximum sensitivity over all possible inputs.
  2. Degree ($deg$): A global algebraic measure. When the function is represented as a real-valued polynomial (its Fourier expansion), what is the highest power of the variables?

For decades, the Sensitivity Conjecture (proposed by Nisan and Szegedy) posited that these two measures are polynomially related: $deg(f) \le s(f)^c$ for some constant $c$. While most other complexity measures, such as decision tree depth or certificate complexity, are known to be polynomially related to each other, sensitivity remained an outlier. Prior to this work, the best-known upper bounds on degree were exponential ($2^s$), leaving a massive gap in our understanding of Boolean function structure.

Bridging the Gap via Approximation

This paper addresses the gap by shifting the focus from exact representation to approximation. Instead of requiring a polynomial to match the function $f$ perfectly, we ask: what is the minimum degree required to get very close to $f$?

Our main result proves that any Boolean function with sensitivity $s$ can be $\epsilon$-approximated in $L_2$ by a polynomial of degree $O(s \log(1/\epsilon))$. This represents a significant breakthrough, moving from a linear dependence on $1/\epsilon$ (the previous folklore bound) to a logarithmic one. This exponential improvement suggests that while sensitivity might not strictly bound the highest-order terms of a polynomial, it exerts strong control over the "mass" of the function's Fourier spectrum.

Methodological Framework

The proof utilizes a combination of combinatorial graph theory and Fourier analysis. Central to the approach are several key techniques:

The Sensitivity Graph and Tree Sensitivity

The authors represent the Boolean hypercube as a Sensitivity Graph ($G_f$), where an edge exists between two inputs if they differ by exactly one bit and produce different outputs. To analyze this graph, they introduce "tree sensitivity"—the size of the largest sensitive tree in $G_f$—and the concept of "proper walks" to relax the rigid constraints of traditional sensitivity.

A New Switching Lemma

A cornerstone of the paper is the development of a "switching lemma for low-sensitivity functions." In the study of $AC^0$ circuits, switching lemmas show that random restrictions (fixing most input bits to constants) simplify functions into low-depth decision trees. The authors prove a similar phenomenon for low-sensitivity functions, showing that after a random restriction, such functions are highly likely to have low decision tree depth.

Combinatorial-Analytic Bridge

By studying the structure of sensitive edges in $G_f$, the authors bound analytic properties of the function. They demonstrate that "complex" Fourier behavior—where energy is spread across high-degree terms—requires the existence of complex structures, such as long proper walks, within the sensitivity graph. This allows them to use combinatorial bounds to constrain the Fourier spectrum.

Key Results and Implications

  • The Main Theorem: For any Boolean function $f$ with sensitivity $s$, there exists a polynomial $p$ of degree $O(s \log(1/\epsilon))$ such that $\mathbb{E}[|p(x) - f(x)|^2] \le \epsilon$.
  • Tightness and the Conjecture: The authors demonstrate that their bound is nearly optimal. Specifically, they show that any further improvement to the power of $s$ or the $\log(1/\epsilon)$ term would actually imply the full Sensitivity Conjecture. This positions the result as the strongest possible statement short of solving the conjecture itself.
  • Learning Algorithms: The results have practical implications for computational learning theory. The authors provide an algorithm to learn "insensitive" functions under the uniform distribution in $n^{O(s \log(1/\epsilon))}$ time.
  • Entropy-Influence: The paper provides new bounds for the Entropy-Influence conjecture, showing that for any Boolean function, the Fourier entropy is $O(I[f] \cdot \log s(f))$, where $I[f]$ is the total influence.

The Robust Sensitivity Conjecture

Beyond the main theorem, the authors propose a "Robust Sensitivity Conjecture." This version suggests that if most inputs to a function have low sensitivity (average sensitivity), then most of the function's Fourier mass must be concentrated on low-degree terms. This robust formulation remains an active area of research, as it seeks to describe the behavior of "typical" inputs rather than just the worst-case maximum sensitivity.

Conclusion

While the full Sensitivity Conjecture was eventually resolved by Hao Huang in 2019 using a concise spectral method, this work remains foundational for its insights into the Fourier concentration of Boolean functions. By proving that low-sensitivity functions are "approximately" low-degree, the authors provided the first major evidence that the local and global complexities of Boolean functions are inextricably linked. The techniques developed here, particularly the switching lemma for sensitivity and the exploration of tree sensitivity, continue to influence the study of computational complexity and Fourier analysis.

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. 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 poly(s). 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 epsilon-approximated (in L_2) by a polynomial whose degree is O(s log(1/epsilon)). This is the first improvement on the folklore bound of s/epsilon. Further, we show that improving the bound to O(s^c log(1/epsilon)^d)$ for any d < 1 and any c > 0 will imply the sensitivity conjecture. Thus our result is essentially the best one can hope for without proving the conjecture. 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, and present an approach towards proving this conjecture.
BibTeX
@inproceedings{gopalan2016degree,
  author = {Parikshit Gopalan and Rocco A. Servedio and Avishay Tal and Avi Wigderson},
  title = {{Degree and Sensitivity: tails of two distributions}},
  booktitle = {Computational Complexity Conference},
  year = {2016},
  url = {https://openreview.net/forum?id=xUOdnHlV4q},
}
Figure