Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.13493 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913033440198656 |
|---|---|
| author | Chen, Yiming |
| author_facet | Chen, Yiming |
| contents | 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$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_13493 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Low-Degree Fourier Threshold for Random Boolean Functions Chen, Yiming Probability 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$ 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. |
| title | Low-Degree Fourier Threshold for Random Boolean Functions |
| topic | Probability |
| url | https://arxiv.org/abs/2604.13493 |