Information theory has a precise 'tipping point': knowing 51% of a system's complexity tells you everything, while 49% tells you nothing.
April 16, 2026
Original Paper
Low-Degree Fourier Threshold for Random Boolean Functions
arXiv · 2604.13493
The Takeaway
Resolving a long-standing question by Vershynin, this paper shows that a random Boolean function is uniquely identified by its Fourier coefficients of degree p/2. It's a binary cliff in information: you either have enough data to reconstruct the entire system, or you are almost entirely in the dark. This has massive implications for data compression, cryptography, and neural network interpretability. It defines exactly how much 'sampling' is required to fully understand a complex random system. For practitioners, it provides a mathematical limit on how little data you can get away with for perfect reconstruction.
From the abstract
We study whether a uniformly random Boolean function $f : \{-1,1\}^p \to \{-1,1\}$ is determined by its Walsh--Fourier coefficients of degree at most $d$. We show that the threshold lies at $p/2$ up to an $O(\sqrt{p \log p})$ window: if \[ d \le \frac{p}{2} - \sqrt{\frac{p}{2}\bigl(\log p + \omega(1)\bigr)}, \] then with probability $1-o(1)$ there exists another Boolean function $g \ne f$ with the same degree-$\le d$ coefficients. Conversely, for every fixed $\eta \in (0,1)$, if \[ d \ge \frac{p