Fourier Analysis of Boolean Functions

This direction is merged into another direction: spectral analysis of Boolean functions. Its last version stays readable and citable here.

Version 1 of 146 papers46 conceptsfrozen 2026-10-04

At first glance, a Boolean function—a rule that takes a string of 0s and 1s and spits out a single 0 or 1—seems purely logical. It is a truth table, a circuit, or a set of "if-then" conditions. However, a powerful research direction treats these discrete logical objects as continuous algebraic ones. By representing Boolean functions as multilinear polynomials, researchers can apply the tools of harmonic analysis to solve problems in social choice, cryptography, and machine learning.

The Spectral Decomposition of Logic

The core intuition of this field is that any Boolean function $f: \{0,1\}^n \to \mathbb{R}$ can be uniquely represented as a sum of "parity functions." In the same way that a complex sound wave can be decomposed into a sum of simple sine waves of different frequencies, a complex logical rule can be decomposed into a sum of XOR operations on different subsets of its inputs.

As Li-Yang Tan notes in the foundational Analysis of Boolean Functions, this Fourier expansion allows us to move from the "spatial domain" (the truth table) to the "spectral domain" (the Fourier coefficients). Each coefficient $\hat{f}(S)$ tells us how much the output of the function depends on a specific subset $S$ of input bits.

This shift is transformative because it turns combinatorial questions into analytical ones. For instance, Steffen Schober and Martin Bossert use this spectral basis in Harmonic Analysis of Boolean Networks: Determinative Power and Perturbations to identify "master" nodes in genetic regulatory networks—nodes whose Fourier coefficients reveal they have high "determinative power" over the system's state.

Quantifying Influence and Noise

One of the most important concepts in this area is Influence. The influence of the $i$-th bit on a function is the probability that flipping that bit changes the output. In the Fourier domain, this has a beautiful representation: it is the sum of the squares of all Fourier coefficients that involve that bit.

This mathematical link allows researchers to prove "impossibility" results with quantitative precision. Consider A Quantitative Arrow Theorem. Kenneth Arrow famously proved that no fair voting system is perfectly rational. By modeling voting rules as functions on a Boolean hypercube, researchers have shown that if a voting system is even slightly far from being a "dictatorship" (where one person's bit determines everything), it must have a non-negligible probability of producing a mathematical paradox.

This relationship between structure and sensitivity is also central to information theory. Ofer Shayevitz and Omri Weinstein have used Fourier analysis to explore the "Most Informative Boolean Function" conjecture, as seen in An Improved Upper Bound for the Most Informative Boolean Function Conjecture. They show that under high noise, the "dictatorship" function is actually the most robust way to transmit information, a result derived by manipulating spectral coefficients.

From Information Theory to Machine Learning

The same "spectral" lens is now being applied to modern artificial intelligence. If a Large Language Model (LLM) or a black-box classifier is viewed as a high-dimensional Boolean function, we can use Fourier tools to "audit" it.

  • Model Auditing: Ayoub Ajarra and colleagues developed the Active Fourier Auditor, which identifies the most influential feature combinations of a model without needing to see its internal weights.
  • Explainability: Bin Yu introduced SPEX, which uses the Hadamard-Fourier Transform to decompose LLM outputs into individual and interacting feature components, making "black box" reasoning transparent.
  • Causal Inference: In Synthetic Combinations, Abhineet Agarwal and Anish Agarwal model combinatorial drug therapies as functions on a hypercube. By using Fourier expansion, they can predict the effect of $2^p$ possible drug combinations using only a small number of observations, effectively "filling in" the spectral coefficients of the treatment space.

Why It Works: The Power of Sparsity

The reason Fourier analysis is so effective across these disparate fields is sparsity. While a Boolean function on $n$ bits has $2^n$ possible Fourier coefficients, most "natural" functions—whether they are voting rules, biological gates, or neural network layers—are dominated by low-degree coefficients.

As Dirk Oliver Theis and Raúl Vicente demonstrate in Partial Information Decomposition of Boolean Functions, concepts like "synergy" and "redundancy" in complex systems map directly to these coefficients. By focusing on the most significant parts of the spectrum, researchers can simplify high-dimensional complexity into a manageable set of influential interactions. This "spectral" view doesn't just describe what a function does; it reveals the underlying architecture of how information flows through it.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fourier_analysis_of_boolean_functions_2e69befb,
  title = {Fourier Analysis of Boolean Functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fourier-analysis-of-boolean-functions/rdr_2e69befbf87542d0b8e5f670d7b1d74c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_fourier_analysis_of_boolean_functions_2e69befb_v1,
  title = {Fourier Analysis of Boolean Functions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fourier-analysis-of-boolean-functions/rdr_2e69befbf87542d0b8e5f670d7b1d74c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}