Low-Degree Fourier Threshold for Random Boolean Functions

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\mathrm{/}2$ up to an $O(\sqrt{p\log p})$ window: if $$d\le \frac{p}{2}-\sqrt{\frac{p}{2}(\log p+\omega (1))},$$ then with probability $1-o(1)$ there exists another Boolean function $g\mathrm{\ne }f$ with the same degree-$\le d$ coefficients. Conversely, for every fixed $\eta \in (0,1)$, if $$d\ge \frac{p}{2}+\sqrt{\frac{p}{2}\log \frac{6p}{{\eta }^2}},$$ then with probability at least $1-2^{-p}$, the function $f$ is uniquely determined by its degree-$\le d$ coefficients, even among all bounded functions $g:\{-1,1{\}}^p\to [-1,1]$. This resolves a question of Vershynin.