Low-Degree Fourier Threshold for Random Boolean Functions

Yiming Chen

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 threshol…