Bounding Fourier Entropy by Total Influence

17 concepts6 papers8 proposals

Every Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ can be viewed through two entirely different lenses: its combinatorial behavior in the spatial domain (how it responds to flipping input bits) and its algebraic behavior in the frequency domain (its Fourier expansion). A central goal in theoretical computer science is understanding how structural simplicity in one domain forces simplicity in the other.

The Fourier Entropy-Influence (FEI) conjecture posits a fundamental bound on this relationship. It asserts that if a function is stable and insensitive on average, its Fourier spectrum must be highly concentrated rather than widely distributed.

The Core Duality: Frequency Spread vs. Input Sensitivity

By Parseval's identity, the squared Fourier coefficients of a Boolean function sum to one ($\sum_S \hat{f}(S)^2 = 1$). This allows us to treat the collection of coefficients $\{\hat{f}(S)^2\}$ as a probability distribution over the subsets $S \subseteq \{1, \dots, n\}$.

We can evaluate this distribution using two distinct metrics:

  1. Fourier Entropy ($H(\hat{f}^2)$): The information-theoretic entropy of this distribution. It measures how "spread out" the function's energy is across different frequencies. If a few coefficients carry all the weight, the entropy is low; if the weight is shattered across many frequencies, the entropy is high.
  2. Total Influence ($\mathbf{I}[f]$): The average sensitivity of the function. It measures the expected number of input coordinate flips that change the function's output. In the Fourier domain, this is equivalent to the weight of the coefficients shifted by the size of their corresponding sets: $\mathbf{I}[f] = \sum_S |S| \hat{f}(S)^2$.

The FEI conjecture states that the Fourier entropy is always bounded above by the total influence times a universal constant $C$:

$$H(\hat{f}^2) \leq C \cdot \mathbf{I}[f]$$

The intuition is that a function with low average sensitivity cannot have an overly complex, chaotic Fourier spectrum. If a function changes its output rarely when inputs are toggled, its energy must be concentrated on a small, predictable set of frequencies.

Verifying the Conjecture for Structural Classes

Because a universal proof for all Boolean functions remains an open challenge, researchers have focused on verifying the conjecture for specific, mathematically well-behaved classes of functions.

Linear threshold functions (LTFs)—which output a bit based on whether a weighted sum of inputs exceeds a threshold—are foundational to machine learning and circuit complexity. Chakraborty et al. proved the FEI conjecture for a broad class of random linear threshold functions. Their work demonstrates that the geometric constraints inherent to thresholding naturally prevent the frequency spectrum from becoming too distributed relative to the function's average sensitivity.

Another strategy is to analyze how these properties behave when functions are nested. Tan et al. established a "composition theorem" for the conjecture. They proved that if a set of base functions satisfies a strengthened version of the FEI conjecture, their composition does as well. The authors used this structural preservation to prove the conjecture for all read-once formulas with bounded-arity gates, while also establishing a sharper lower bound for the universal constant ($C \geq 6.278$).

Structural Complexity as a Proxy for Entropy

To bound Fourier entropy without computing every individual coefficient, researchers often look at combinatorial proxies that dictate how easily a function can be evaluated.

One such proxy is certificate complexity—the minimum number of input bits that must be revealed to definitively fix the function's output. In a pair of closely related papers, Srinivasan A et al. (2020) and Srinivasan A et al. (2021) introduced a novel measure called average unambiguous parity-certificate complexity. By tracking how efficiently a function can be verified via parity checks, the authors derived tighter upper bounds on Fourier entropy and made significant progress on the weaker Fourier Min-Entropy-Influence (FMEI) conjecture.

Alternatively, the global entropy can be bounded by combining average-case sensitivity with worst-case sensitivity. Gopalan et al. proved that the Fourier entropy of a Boolean function is bounded by the product of its total influence and the logarithm of its max sensitivity ($s$). This result bridges the gap between local smoothness and global algebraic complexity, showing that even if a function has high worst-case sensitivity, its spectral entropy remains constrained if its average sensitivity is low.

Generalizing Beyond Uniform Measures

The classical formulation of the FEI conjecture assumes that inputs are drawn from a uniform distribution. However, real-world applications—such as analyzing biased random walks or specific learning models—require understanding how these properties behave under biased product measures, where bits are more likely to be $1$ than $-1$.

Keller et al. successfully extended the framework to biased measures, demonstrating that the entropy bound scales predictably with the inherent entropy of the underlying biased bits. Furthermore, the authors established a universal upper bound that constrains spectral entropy using both total influence and the total number of input variables ($n$). This loose but guaranteed ceiling connects the FEI conjecture to the study of juntas—functions whose outputs depend entirely on a small, fixed subset of coordinates—confirming that highly concentrated variable dependency forces a corresponding concentration in the Fourier spectrum.

Key Foundational Work

A note on the Entropy/Influence conjecture (2012) — contributed 6 concept elements to this direction.
A composition theorem for the Fourier Entropy-Influence conjecture (2013) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_boolean_function_sensitivity_bounds_fbfa062f,
  title = {Boolean function sensitivity bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/boolean-function-sensitivity-bounds/rdr_fbfa062f28ac4e469acf54595ab50527},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_boolean_function_sensitivity_bounds_fbfa062f_v1,
  title = {Boolean function sensitivity bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/boolean-function-sensitivity-bounds/rdr_fbfa062f28ac4e469acf54595ab50527/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake