Boolean Functions with Minimal Spectral Sensitivity
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917930455793664 |
|---|---|
| author | Prūsis, Krišjānis Vihrovs, Jevgēnijs |
| author_facet | Prūsis, Krišjānis Vihrovs, Jevgēnijs |
| contents | We show examples of total Boolean functions that depend on $n$ variables and have spectral sensitivity $Θ(\sqrt{\log n})$, which is asymptotically minimal. Our main new function combines the Hamming code with the Boolean address function and has $λ(f) = \sqrt{(1+o(1)) \log_2 n}$, which is optimal even up to a constant factor. By combining this function with itself in a specific way, we also obtain a family of functions with $\text{s}_0(f) = (c+o(1)) \log_2 n$ and $\text{s}_0(f) = (1-c+o(1)) \log_2 n$ for any $c \in [0,1]$. This is an optimal tradeoff for Boolean functions with low sensitivity, as the lower bound on sensitivity by Simon generalizes to \[\text{s}_0(f)+\text{s}_1(f)\geq\log_2 n - \log_2 \log_2 n + 2.\] As a corollary, this gives a new example of a function with minimal possible sensitivity (up to a constant factor), $\text{s}(f) = (\frac{1}{2}+o(1)) \log_2 n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_16088 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Boolean Functions with Minimal Spectral Sensitivity Prūsis, Krišjānis Vihrovs, Jevgēnijs Computational Complexity We show examples of total Boolean functions that depend on $n$ variables and have spectral sensitivity $Θ(\sqrt{\log n})$, which is asymptotically minimal. Our main new function combines the Hamming code with the Boolean address function and has $λ(f) = \sqrt{(1+o(1)) \log_2 n}$, which is optimal even up to a constant factor. By combining this function with itself in a specific way, we also obtain a family of functions with $\text{s}_0(f) = (c+o(1)) \log_2 n$ and $\text{s}_0(f) = (1-c+o(1)) \log_2 n$ for any $c \in [0,1]$. This is an optimal tradeoff for Boolean functions with low sensitivity, as the lower bound on sensitivity by Simon generalizes to \[\text{s}_0(f)+\text{s}_1(f)\geq\log_2 n - \log_2 \log_2 n + 2.\] As a corollary, this gives a new example of a function with minimal possible sensitivity (up to a constant factor), $\text{s}(f) = (\frac{1}{2}+o(1)) \log_2 n$. |
| title | Boolean Functions with Minimal Spectral Sensitivity |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2412.16088 |