A new bound for the Fourier-Entropy-Influence conjecture
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908703865700352 |
|---|---|
| author | Han, Xiao |
| author_facet | Han, Xiao |
| contents | In this paper, we prove that the Fourier entropy of an $n$-dimensional boolean function $f$ can be upper-bounded by $O(I(f)+ \sum\limits_{k\in[n]}I_k(f)\log \frac{1}{I_k(f)})$, where $I(f)$ is its total influence and $I_k(f)$ is the influence of the $k$-th coordinate. The proof is elementary and uses iterative bounds on moments of Fourier coefficients over different levels. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_08271 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A new bound for the Fourier-Entropy-Influence conjecture Han, Xiao Combinatorics Functional Analysis In this paper, we prove that the Fourier entropy of an $n$-dimensional boolean function $f$ can be upper-bounded by $O(I(f)+ \sum\limits_{k\in[n]}I_k(f)\log \frac{1}{I_k(f)})$, where $I(f)$ is its total influence and $I_k(f)$ is the influence of the $k$-th coordinate. The proof is elementary and uses iterative bounds on moments of Fourier coefficients over different levels. |
| title | A new bound for the Fourier-Entropy-Influence conjecture |
| topic | Combinatorics Functional Analysis |
| url | https://arxiv.org/abs/2312.08271 |