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/2$ up to an $O(\sqrt{p \log p})$ window: if \[ d \le \frac{p}{2} - \sqrt{\frac{p}{2}\bigl(\log p + ω(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 $η\in (0,1)$, if \[ d \ge \frac{p}{2} + \sqrt{\frac{p}{2}\log\frac{6p}{η^2}}, \] then with probability at least $1-2^{-p}$, the function $f$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.13493
curl -X POST /api/v1/records/arxiv/2604.13493/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.13493/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'